126212024-12-26 22:44:39BucsMateA lehető legkevesebb átszállás (50 pont)cpp17Hibás válasz 34/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;
    }*/

    return v1.kezd < v2.kezd;
}

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(jelenlegi_vonat);
    while(vonatok[jelenlegi_vonat].veg != M){
        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(jelenlegi_vonat);
    }

    cout << megoldas.size() - 1 << endl;
    for(int i = 0; i < megoldas.size(); i++){
        cout << megoldas[i] + 1 << " ";
    }
    cout << endl;

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base34/50
1Elfogadva0/01ms320 KiB
2Hibás válasz0/08ms500 KiB
3Hibás válasz0/11ms320 KiB
4Hibás válasz0/11ms320 KiB
5Elfogadva2/21ms332 KiB
6Elfogadva2/21ms380 KiB
7Elfogadva2/22ms324 KiB
8Elfogadva2/22ms320 KiB
9Részben helyes1/22ms320 KiB
10Részben helyes1/23ms320 KiB
11Részben helyes1/23ms320 KiB
12Részben helyes1/24ms320 KiB
13Részben helyes1/21ms500 KiB
14Részben helyes1/22ms320 KiB
15Részben helyes1/23ms320 KiB
16Részben helyes1/24ms320 KiB
17Részben helyes1/26ms484 KiB
18Részben helyes1/26ms320 KiB
19Részben helyes1/27ms500 KiB
20Részben helyes1/27ms508 KiB
21Részben helyes1/28ms320 KiB
22Részben helyes1/28ms320 KiB
23Elfogadva2/27ms524 KiB
24Elfogadva2/28ms520 KiB
25Elfogadva2/28ms520 KiB
26Elfogadva2/27ms360 KiB
27Elfogadva2/27ms520 KiB
28Elfogadva2/27ms516 KiB