124862024-12-19 08:50:11feheristvanA lehető legkevesebb átszállás (50 pont)cpp17Időlimit túllépés 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base3/50
1Időlimit túllépés0/0284ms320 KiB
2Időlimit túllépés0/0284ms320 KiB
3Időlimit túllépés0/1284ms320 KiB
4Hibás válasz0/11ms324 KiB
5Időlimit túllépés0/2300ms320 KiB
6Hibás válasz0/21ms512 KiB
7Időlimit túllépés0/2275ms320 KiB
8Időlimit túllépés0/2275ms508 KiB
9Időlimit túllépés0/2300ms320 KiB
10Időlimit túllépés0/2300ms320 KiB
11Időlimit túllépés0/2289ms320 KiB
12Időlimit túllépés0/2289ms320 KiB
13Időlimit túllépés0/2298ms320 KiB
14Időlimit túllépés0/2300ms320 KiB
15Időlimit túllépés0/2272ms508 KiB
16Időlimit túllépés0/2273ms320 KiB
17Időlimit túllépés0/2298ms320 KiB
18Időlimit túllépés0/2300ms320 KiB
19Időlimit túllépés0/2286ms320 KiB
20Időlimit túllépés0/2287ms500 KiB
21Időlimit túllépés0/2300ms320 KiB
22Időlimit túllépés0/2300ms320 KiB
23Hibás válasz0/27ms320 KiB
24Hibás válasz0/28ms320 KiB
25Részben helyes1/28ms520 KiB
26Hibás válasz0/27ms320 KiB
27Részben helyes1/27ms524 KiB
28Részben helyes1/27ms536 KiB