126232024-12-26 22:52:08BucsMateA lehető legkevesebb átszállás (50 pont)cpp17Wrong answer 49/508ms524 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Vonat
{
    int sorszam, kezd, veg;
};

bool hasonlit(Vonat v1, Vonat v2)
{
    if(v1.kezd != v2.kezd){
        return v1.kezd < v2.kezd;
    }
    else{
        return v1.veg > v2.veg;
    }
}

int main()
{
    int N, M;
    cin >> N >> M;
    vector<Vonat> vonatok(N);
    vector<int> megoldas;

    for(int i = 0; i < N; i++){
        int a, b;
        cin >> a >> b;
        vonatok[i] = {i+1, a, b};
    }
    sort(vonatok.begin(), vonatok.end(), hasonlit);

    int jelenlegi_vonat = -1;
    int max_veg = 0;
    for(int i = 0; i < N && vonatok[i].kezd == 1; i++){
        if(vonatok[i].veg > max_veg){
            max_veg = vonatok[i].veg;
            jelenlegi_vonat = i;
        }
    }
    if(jelenlegi_vonat == -1){
        cout << -1 << endl;
        return 0;
    }
    megoldas.push_back(vonatok[jelenlegi_vonat].sorszam);
    while(vonatok[jelenlegi_vonat].veg != M && jelenlegi_vonat < N){
        int kovetkezo_vonat = jelenlegi_vonat+1;
        for(int i = jelenlegi_vonat+1; i < N && vonatok[i].kezd <= vonatok[jelenlegi_vonat].veg; i++){
            if(vonatok[i].veg > max_veg){
                max_veg = vonatok[i].veg;
                kovetkezo_vonat = i;
            }
        }
        jelenlegi_vonat = kovetkezo_vonat;
        megoldas.push_back(vonatok[jelenlegi_vonat].sorszam);
    }
    if(vonatok[jelenlegi_vonat].veg != M){
        cout << -1 << endl;
        return 0;
    }
    sort(megoldas.begin(), megoldas.end());
    cout << megoldas.size() - 1 << endl;
    for(int i = 0; i < megoldas.size(); i++){
        cout << megoldas[i] << " ";
    }
    cout << endl;

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base49/50
1Accepted0/01ms320 KiB
2Accepted0/08ms320 KiB
3Accepted1/11ms320 KiB
4Wrong answer0/11ms320 KiB
5Accepted2/21ms320 KiB
6Accepted2/21ms320 KiB
7Accepted2/22ms320 KiB
8Accepted2/22ms336 KiB
9Accepted2/22ms320 KiB
10Accepted2/23ms440 KiB
11Accepted2/24ms444 KiB
12Accepted2/24ms460 KiB
13Accepted2/21ms320 KiB
14Accepted2/22ms320 KiB
15Accepted2/23ms500 KiB
16Accepted2/24ms324 KiB
17Accepted2/26ms372 KiB
18Accepted2/27ms496 KiB
19Accepted2/27ms320 KiB
20Accepted2/27ms512 KiB
21Accepted2/28ms520 KiB
22Accepted2/28ms524 KiB
23Accepted2/27ms524 KiB
24Accepted2/28ms320 KiB
25Accepted2/28ms516 KiB
26Accepted2/27ms320 KiB
27Accepted2/28ms320 KiB
28Accepted2/27ms500 KiB