45302023-03-29 12:50:58TomaSajtA lehető legkevesebb átszállás (50 pont)cpp17Accepted 50/504ms4620 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;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms1828 KiB
2Accepted0/04ms2272 KiB
3Accepted1/13ms2228 KiB
4Accepted1/13ms2440 KiB
5Accepted2/23ms2800 KiB
6Accepted2/22ms2748 KiB
7Accepted2/23ms2892 KiB
8Accepted2/23ms3236 KiB
9Accepted2/23ms3348 KiB
10Accepted2/23ms3304 KiB
11Accepted2/23ms3424 KiB
12Accepted2/24ms3532 KiB
13Accepted2/23ms3500 KiB
14Accepted2/23ms3512 KiB
15Accepted2/23ms3848 KiB
16Accepted2/24ms3764 KiB
17Accepted2/24ms3908 KiB
18Accepted2/24ms4192 KiB
19Accepted2/24ms4284 KiB
20Accepted2/24ms4288 KiB
21Accepted2/24ms4296 KiB
22Accepted2/24ms4532 KiB
23Accepted2/24ms4504 KiB
24Accepted2/24ms4504 KiB
25Accepted2/24ms4620 KiB
26Accepted2/24ms4504 KiB
27Accepted2/24ms4512 KiB
28Accepted2/24ms4508 KiB