124902024-12-19 10:59:21feheristvanA lehető legkevesebb átszállás (50 pont)cpp17Wrong answer 5/508ms528 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <tuple>

using namespace std;

struct vonat{
    int veg, kezd, ind;
};
/*
int main()
{
    long n, m;
    cin >> n >> m;
    vector <vonat> a;
    a.resize(n);
    vector <int> gyak;
    gyak.resize(m);
    for(int i = 0; i < n; i ++){
        cin >> a[i].kezd >> a[i].veg;
        a[i].ind = i;
        for(int j = a[i].kezd; j <= a[i].veg; j ++){
            gyak[j] ++;
        }
    }
  //  bubbleSort(a);
    int j = 0, mv = 0;
    vector <int> vegso;
    for(int i = 0 ; i < n; i ++){
        j = i + 1;
        mv = a[i].veg;
        while(a[i].kezd == a[j].kezd){
            if(mv < a[j].veg)
                mv = a[j].veg;
            j ++;
        }
       // cout << mv;
        while(gyak[mv] <= 1 and mv >= 0){
          //  cout << gyak[mv] << " " ;
            mv --;
        }
        if(mv < 0){
            cout << "-1";
            return 0;
        }
        else if(gyak[mv] > 1){
            vegso.push_back(a[mv].ind);
        }
    }
    cout << vegso.size() << endl;
    for(auto i : vegso)
        cout << i << " ";
    return 0;
} */

/*
int main(){
    vector <int> a;
    a.push_back(0);
    vector <pair <int, int>> vonat;
    int elozo = 0;
    int maxi = 0;
    pair <int, int> jelenleg;
    int maxveg = 0;
    long n, m;
    cin >> n >> m;
    cin >> jelenleg.first >> jelenleg.second;
    vonat.push_back(jelenleg);
    int db = 0;
    for(int i = 1 ; i < n; i ++){
        cin >> jelenleg.first >> jelenleg.second;
        vonat.push_back(jelenleg);
        a.push_back(i);
        if(jelenleg.first == vonat[elozo].first and jelenleg.second > vonat[elozo].second){
            elozo = i;
            maxi = i;
            a.pop_back();
            a.push_back(i);
        }
        else if(jelenleg.first <= vonat[elozo].second and jelenleg.second > vonat[elozo].second and jelenleg.second > vonat[maxi].second){
            maxi = i;
            a.pop_back();
            a.push_back(i);
        }
        else if(jelenleg.first > vonat[elozo].second){
            if(vonat[maxi].first < vonat[elozo].second){
                cout << "-1";
                return 0;
            }
            else{

            }
        }
    }
    for(auto i : a)
        cout << i << " ";
}
*/

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 = 0, farthest = 0, indx = 0, i;
    while(current_end < m){
        current_end = trains[indx].veg;
        i = indx;
        while(trains[indx].kezd == trains[indx + 1].kezd){
            if(trains[indx].veg < trains[indx + 1].veg){
                current_end = trains[indx + 1].veg;
                i = indx;
            }
            indx ++;
        }
        indx = i;
        while(indx < n and trains[indx].kezd <= current_end and !trains.empty()){
            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
base5/50
1Wrong answer0/01ms320 KiB
2Wrong answer0/08ms320 KiB
3Accepted1/11ms320 KiB
4Wrong answer0/11ms320 KiB
5Partially correct1/21ms320 KiB
6Wrong answer0/21ms320 KiB
7Wrong answer0/21ms412 KiB
8Wrong answer0/22ms420 KiB
9Wrong answer0/22ms360 KiB
10Wrong answer0/23ms436 KiB
11Wrong answer0/23ms324 KiB
12Wrong answer0/24ms320 KiB
13Wrong answer0/22ms520 KiB
14Wrong answer0/22ms508 KiB
15Wrong answer0/23ms320 KiB
16Wrong answer0/24ms464 KiB
17Wrong answer0/24ms484 KiB
18Wrong answer0/26ms388 KiB
19Wrong answer0/26ms320 KiB
20Wrong answer0/27ms508 KiB
21Wrong answer0/27ms320 KiB
22Wrong answer0/27ms520 KiB
23Partially correct1/27ms516 KiB
24Partially correct1/27ms528 KiB
25Wrong answer0/27ms520 KiB
26Partially correct1/27ms320 KiB
27Wrong answer0/27ms320 KiB
28Wrong answer0/27ms320 KiB