124892024-12-19 10:57:32feheristvanA lehető legkevesebb átszállás (50 pont)cpp17Wrong answer 2/508ms684 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; // Corrected to read 'veg'
        trains[i].ind = i;
    }

    // Sort trains by starting time
    sort(trains.begin(), trains.end(), [](const vonat &a, const vonat &b) {
        return a.kezd < b.kezd;
    });

    int current_end = 0, farthest = 0, indx = 0;

    while (current_end < m) {
        // Find the farthest train we can reach from current_end
        while (indx < n && trains[indx].kezd <= current_end) {
            farthest = max(farthest, trains[indx].veg);
            indx++;
        }

        // If we cannot move forward, return -1
        if (farthest <= current_end) {
            cout << "-1"; // No further progress can be made
            return 0;
        }

        // Update current_end to the farthest we can reach
        current_end = farthest;

        // Store the index of the last train used
        selected_trains.push_back(trains[indx - 1].ind);
        
        // Handle the case where multiple trains start at the same time
        while (indx < n - 1 && trains[indx].kezd == trains[indx + 1].kezd) {
            if (trains[indx].veg < trains[indx + 1].veg) {
                current_end = trains[indx + 1].veg;
            }
            indx++;
        }
    }

    cout << selected_trains.size() << endl;
    for (auto i : selected_trains) {
        cout << i << " ";
    }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base2/50
1Wrong answer0/01ms500 KiB
2Wrong answer0/08ms508 KiB
3Accepted1/11ms320 KiB
4Accepted1/11ms320 KiB
5Wrong answer0/21ms320 KiB
6Wrong answer0/21ms320 KiB
7Wrong answer0/21ms320 KiB
8Wrong answer0/22ms320 KiB
9Wrong answer0/22ms424 KiB
10Wrong answer0/23ms436 KiB
11Wrong answer0/23ms360 KiB
12Wrong answer0/24ms456 KiB
13Wrong answer0/21ms320 KiB
14Wrong answer0/22ms320 KiB
15Wrong answer0/23ms508 KiB
16Wrong answer0/24ms320 KiB
17Wrong answer0/26ms684 KiB
18Wrong answer0/26ms320 KiB
19Wrong answer0/26ms504 KiB
20Wrong answer0/27ms500 KiB
21Wrong answer0/27ms320 KiB
22Wrong answer0/27ms320 KiB
23Wrong answer0/27ms320 KiB
24Wrong answer0/27ms320 KiB
25Wrong answer0/27ms320 KiB
26Wrong answer0/27ms516 KiB
27Wrong answer0/27ms320 KiB
28Wrong answer0/27ms320 KiB