124862024-12-19 08:50:11feheristvanA lehető legkevesebb átszállás (50 pont)cpp17Time limit exceeded 3/50300ms536 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct vonat{
    int veg, kezd, ind;
};

int main(){
    vector <vonat> trains;
    vector <int> selected_trains;
    int n, m;
    cin >> n >> m;
    trains.resize(n);
    for(int i = 0 ; i < n; i ++){
        cin >> trains[i].kezd >> trains[i].veg;
        trains[i].ind = i;
    }
    int current_end = trains[0].veg, farthest = trains[0].veg, indx = 0;
    selected_trains.push_back(indx);
    while(trains[indx].kezd == trains[indx + 1].kezd){
        if(trains[indx].veg < trains[indx + 1].veg){
            farthest = trains[indx + 1].veg;
            current_end = trains[indx + 1].veg;
            selected_trains.pop_back();
            selected_trains.push_back(trains[indx + 1].ind);
        }
    }
    while(current_end < m){
        current_end = trains[indx].veg;
        while(indx < n and trains[indx].kezd <= current_end){
            farthest = max(trains[indx].veg, farthest);
            indx ++;
        }
        if(farthest < current_end){
            cout << "-1";
            return 0;
        }
        current_end = farthest;
        selected_trains.push_back(trains[indx - 1].ind);
    }
    cout << selected_trains.size() - 1 << endl;
    for(auto i : selected_trains)
        cout << i << " ";
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base3/50
1Time limit exceeded0/0284ms320 KiB
2Time limit exceeded0/0284ms320 KiB
3Time limit exceeded0/1284ms320 KiB
4Wrong answer0/11ms324 KiB
5Time limit exceeded0/2300ms320 KiB
6Wrong answer0/21ms512 KiB
7Time limit exceeded0/2275ms320 KiB
8Time limit exceeded0/2275ms508 KiB
9Time limit exceeded0/2300ms320 KiB
10Time limit exceeded0/2300ms320 KiB
11Time limit exceeded0/2289ms320 KiB
12Time limit exceeded0/2289ms320 KiB
13Time limit exceeded0/2298ms320 KiB
14Time limit exceeded0/2300ms320 KiB
15Time limit exceeded0/2272ms508 KiB
16Time limit exceeded0/2273ms320 KiB
17Time limit exceeded0/2298ms320 KiB
18Time limit exceeded0/2300ms320 KiB
19Time limit exceeded0/2286ms320 KiB
20Time limit exceeded0/2287ms500 KiB
21Time limit exceeded0/2300ms320 KiB
22Time limit exceeded0/2300ms320 KiB
23Wrong answer0/27ms320 KiB
24Wrong answer0/28ms320 KiB
25Partially correct1/28ms520 KiB
26Wrong answer0/27ms320 KiB
27Partially correct1/27ms524 KiB
28Partially correct1/27ms536 KiB