124892024-12-19 10:57:32feheristvanA lehető legkevesebb átszállás (50 pont)cpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base2/50
1Hibás válasz0/01ms500 KiB
2Hibás válasz0/08ms508 KiB
3Elfogadva1/11ms320 KiB
4Elfogadva1/11ms320 KiB
5Hibás válasz0/21ms320 KiB
6Hibás válasz0/21ms320 KiB
7Hibás válasz0/21ms320 KiB
8Hibás válasz0/22ms320 KiB
9Hibás válasz0/22ms424 KiB
10Hibás válasz0/23ms436 KiB
11Hibás válasz0/23ms360 KiB
12Hibás válasz0/24ms456 KiB
13Hibás válasz0/21ms320 KiB
14Hibás válasz0/22ms320 KiB
15Hibás válasz0/23ms508 KiB
16Hibás válasz0/24ms320 KiB
17Hibás válasz0/26ms684 KiB
18Hibás válasz0/26ms320 KiB
19Hibás válasz0/26ms504 KiB
20Hibás válasz0/27ms500 KiB
21Hibás válasz0/27ms320 KiB
22Hibás válasz0/27ms320 KiB
23Hibás válasz0/27ms320 KiB
24Hibás válasz0/27ms320 KiB
25Hibás válasz0/27ms320 KiB
26Hibás válasz0/27ms516 KiB
27Hibás válasz0/27ms320 KiB
28Hibás válasz0/27ms320 KiB