7342 2024. 01. 07 21:44:06 szabelr A lehető legkevesebb átszállás (50 pont) cpp17 Elfogadva 50/50 9ms 4024 KiB
#include <iostream>
#include <algorithm>

using namespace std;

struct VonatInfo {
    int sorszam;
    int start;
    int stop;
};

bool kisebbVonat(VonatInfo v1, VonatInfo v2) {
    return v1.start < v2.start;
}

int main() {

    VonatInfo A[10000];
    int hasznaltVonat[10000];
    int N, M;
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        int start, stop;
        cin >> start >> stop;
        A[i].sorszam = i + 1;
        A[i].start = start;
        A[i].stop = stop;
    }

    sort(A, A+N, kisebbVonat);

    int hol = 1, maxAllomas = 1;
    int K = 0;
    int i = 0;
    int maxHasznaltVonat;

    bool eljut = true;

    while (eljut && hol < M) {
        maxAllomas = hol;
        while (i<N and A[i].start <= hol) {
            if (A[i].stop > maxAllomas) {
                maxAllomas = A[i].stop;
                maxHasznaltVonat = A[i].sorszam;
            }
            i++;
        }
        if (hol != maxAllomas) {
            hol = maxAllomas;
            hasznaltVonat[K++] = maxHasznaltVonat;
        }
        else {
            eljut = false;
        }
    }

    if (eljut) {
        cout << K-1 << endl;

        sort(hasznaltVonat, hasznaltVonat+K);
        for (int i = 0; i < K; i++) cout << hasznaltVonat[i] << " ";
    }
    else {
        cout << "-1";
    }

    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 2156 KiB
2 Elfogadva 0/0 9ms 2376 KiB
3 Elfogadva 1/1 3ms 2584 KiB
4 Elfogadva 1/1 3ms 2916 KiB
5 Elfogadva 2/2 3ms 3032 KiB
6 Elfogadva 2/2 3ms 2892 KiB
7 Elfogadva 2/2 3ms 2900 KiB
8 Elfogadva 2/2 4ms 2896 KiB
9 Elfogadva 2/2 4ms 2956 KiB
10 Elfogadva 2/2 4ms 2956 KiB
11 Elfogadva 2/2 4ms 2956 KiB
12 Elfogadva 2/2 6ms 3080 KiB
13 Elfogadva 2/2 3ms 3184 KiB
14 Elfogadva 2/2 4ms 3304 KiB
15 Elfogadva 2/2 4ms 3532 KiB
16 Elfogadva 2/2 6ms 3584 KiB
17 Elfogadva 2/2 8ms 3724 KiB
18 Elfogadva 2/2 8ms 3800 KiB
19 Elfogadva 2/2 8ms 3804 KiB
20 Elfogadva 2/2 8ms 3804 KiB
21 Elfogadva 2/2 8ms 3892 KiB
22 Elfogadva 2/2 9ms 3900 KiB
23 Elfogadva 2/2 8ms 3800 KiB
24 Elfogadva 2/2 8ms 3892 KiB
25 Elfogadva 2/2 8ms 3804 KiB
26 Elfogadva 2/2 8ms 3804 KiB
27 Elfogadva 2/2 8ms 3804 KiB
28 Elfogadva 2/2 8ms 4024 KiB