124822024-12-19 08:16:16feheristvanA lehető legkevesebb átszállás (50 pont)cpp17Wrong answer 2/508ms760 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct vonat {
    int kezd, veg, ind;  // Starting time, ending time, and index of the train
};

// Function to compare trains by start time (and end time in case of tie)
bool compare(vonat a, vonat b) {
    return a.kezd < b.kezd;
}

int main() {
    long n, m;
    cin >> n >> m;

    vector<vonat> trains(n); // Vector to hold train schedules

    // Input train data
    for (int i = 0; i < n; i++) {
        cin >> trains[i].kezd >> trains[i].veg;
        trains[i].ind = i + 1;  // Store the index of the train
    }

    // Sort trains by start time, and by end time in case of tie
    sort(trains.begin(), trains.end(), compare);

    vector<int> selected_trains;  // Vector to store indices of selected trains
    int current_end = 0;          // The current position we need to reach
    int idx = 0;                  // Index for traversing the trains
    int farthest = 0;             // The farthest we can reach with the current train sequence

    // Greedily pick the minimum number of trains
    while (current_end < m) {
        // Find the farthest train that starts before or at current_end
        while (idx < n && trains[idx].kezd <= current_end) {
            farthest = max(farthest, trains[idx].veg);
            idx++;
        }

        // If no train can extend our reach, we are stuck
        if (farthest <= current_end) {
            cout << -1 << endl;
            return 0;
        }

        // Move to the farthest position and add this train to the selection
        current_end = farthest;
        selected_trains.push_back(trains[idx - 1].ind);  // Store the index of the selected train
    }

    // Output the count of trains and their indices
    cout << selected_trains.size() << endl;
    for (int i = 0; i < selected_trains.size(); i++) {
        cout << selected_trains[i] << " ";
    }
    cout << endl;

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base2/50
1Wrong answer0/01ms320 KiB
2Wrong answer0/08ms320 KiB
3Accepted1/11ms500 KiB
4Accepted1/11ms320 KiB
5Wrong answer0/21ms320 KiB
6Wrong answer0/21ms320 KiB
7Wrong answer0/21ms320 KiB
8Wrong answer0/22ms320 KiB
9Wrong answer0/22ms320 KiB
10Wrong answer0/23ms384 KiB
11Wrong answer0/23ms320 KiB
12Wrong answer0/24ms500 KiB
13Wrong answer0/21ms500 KiB
14Wrong answer0/22ms424 KiB
15Wrong answer0/23ms360 KiB
16Wrong answer0/24ms396 KiB
17Wrong answer0/26ms484 KiB
18Wrong answer0/26ms500 KiB
19Wrong answer0/27ms504 KiB
20Wrong answer0/28ms320 KiB
21Wrong answer0/28ms320 KiB
22Wrong answer0/28ms572 KiB
23Wrong answer0/27ms320 KiB
24Wrong answer0/27ms500 KiB
25Wrong answer0/27ms320 KiB
26Wrong answer0/27ms348 KiB
27Wrong answer0/27ms320 KiB
28Wrong answer0/27ms760 KiB