4530 2023. 03. 29 12:50:58 TomaSajt A lehető legkevesebb átszállás (50 pont) cpp17 Elfogadva 50/50 4ms 4620 KiB
#include <bits/stdc++.h>
using namespace std;
#define speed cin.tie(0); ios::sync_with_stdio(0)

struct line {
    int s, e, id;
};

int main() {
    speed;
    int n, m; cin >> n >> m;
    vector<line> lines(n);
    for (int j = 0; j < n; j++) {
        cin >> lines[j].s >> lines[j].e;
        lines[j].id = j + 1;
    }
    int loc = 1;
    int i = 0;
    vector<int> sol;
    while (loc < m && i < n) {
        int bestI = -1;
        while (i < n && lines[i].s <= loc) {
            int bestE = bestI == -1 ? -1 : lines[bestI].e;
            if (lines[i].e > bestE) bestI = i;
            i++;
        }
        if (bestI == -1) break;
        loc = lines[bestI].e;
        sol.push_back(lines[bestI].id);
    }
    if (loc != m) {
        cout << "-1";
    }
    else {
        cout << sol.size() - 1 << '\n';
        for (auto j : sol) cout << j << ' ';
    }
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1828 KiB
2 Elfogadva 0/0 4ms 2272 KiB
3 Elfogadva 1/1 3ms 2228 KiB
4 Elfogadva 1/1 3ms 2440 KiB
5 Elfogadva 2/2 3ms 2800 KiB
6 Elfogadva 2/2 2ms 2748 KiB
7 Elfogadva 2/2 3ms 2892 KiB
8 Elfogadva 2/2 3ms 3236 KiB
9 Elfogadva 2/2 3ms 3348 KiB
10 Elfogadva 2/2 3ms 3304 KiB
11 Elfogadva 2/2 3ms 3424 KiB
12 Elfogadva 2/2 4ms 3532 KiB
13 Elfogadva 2/2 3ms 3500 KiB
14 Elfogadva 2/2 3ms 3512 KiB
15 Elfogadva 2/2 3ms 3848 KiB
16 Elfogadva 2/2 4ms 3764 KiB
17 Elfogadva 2/2 4ms 3908 KiB
18 Elfogadva 2/2 4ms 4192 KiB
19 Elfogadva 2/2 4ms 4284 KiB
20 Elfogadva 2/2 4ms 4288 KiB
21 Elfogadva 2/2 4ms 4296 KiB
22 Elfogadva 2/2 4ms 4532 KiB
23 Elfogadva 2/2 4ms 4504 KiB
24 Elfogadva 2/2 4ms 4504 KiB
25 Elfogadva 2/2 4ms 4620 KiB
26 Elfogadva 2/2 4ms 4504 KiB
27 Elfogadva 2/2 4ms 4512 KiB
28 Elfogadva 2/2 4ms 4508 KiB