69352023-12-20 18:53:58MagyarKendeSZLGA lehető legkevesebb átszállás (50 pont)cpp17Accepted 50/504ms4832 KiB
#include <iostream>
#include <vector>
#include <array>
#include <queue>

using namespace std;

using Pair = array<int, 2>;

void init() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(0);
}

int main() {
    init();

    int N, M;
    cin >> N >> M;

    vector<Pair> TS(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> TS[i][0] >> TS[i][1];
    }

    vector<int> path;
    int i = 1, pos = 1, curr;

    while (pos < M) {
        curr = -1;

        while (i <= N && TS[i][0] <= pos) {
            if (curr == -1 || TS[curr][1] < TS[i][1]) curr = i;
            i++;
        }

        if (curr == -1) { // impossible part
            cout << -1;
            exit(0);
        }

        pos = TS[curr][1];
        path.push_back(curr);
    }

    cout << path.size() - 1 << '\n';
    for (int n : path)  {
        cout << n << ' ';
    }

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms1832 KiB
2Accepted0/04ms2232 KiB
3Accepted1/13ms2444 KiB
4Accepted1/13ms2500 KiB
5Accepted2/23ms2644 KiB
6Accepted2/23ms2848 KiB
7Accepted2/23ms3076 KiB
8Accepted2/23ms3408 KiB
9Accepted2/23ms3612 KiB
10Accepted2/23ms3708 KiB
11Accepted2/24ms3588 KiB
12Accepted2/24ms3600 KiB
13Accepted2/23ms3752 KiB
14Accepted2/23ms3848 KiB
15Accepted2/23ms4176 KiB
16Accepted2/24ms4464 KiB
17Accepted2/24ms4596 KiB
18Accepted2/24ms4600 KiB
19Accepted2/24ms4832 KiB
20Accepted2/24ms4628 KiB
21Accepted2/24ms4644 KiB
22Accepted2/24ms4640 KiB
23Accepted2/24ms4636 KiB
24Accepted2/24ms4636 KiB
25Accepted2/24ms4636 KiB
26Accepted2/24ms4644 KiB
27Accepted2/24ms4652 KiB
28Accepted2/24ms4644 KiB