7686 2024. 01. 10 13:11:14 adam A lehető legkevesebb átszállás (50 pont) cpp17 Hibás válasz 2/50 268ms 4844 KiB
#include <bits/stdc++.h>
using namespace std;

pair<int, int> get_longest (pair<int, int> from, vector<pair<int, int>> trains) {
    pair<int, int> highest;
    for (int i = 0; i < trains.size(); i++) {
        if (trains[i].first - 1 <= from.second && trains[i].second <= trains[i].second)
            if (trains[i].second > highest.second)
                highest = pair(i, trains[i].second - 1);
    }
    return highest;

}

int main() {
    cin.tie(nullptr );
    ios_base::sync_with_stdio(false);
    int train_count = 0;
    int station_count = 0;
    cin >> train_count >> station_count;
    vector<pair<int, int>> trains(train_count, pair(0, 0));
    vector<int> stations(station_count, 0);


    for (int i = 0; i < train_count; i++) {
        pair<int, int> train_stops;
        cin >> train_stops.first >> train_stops.second;
        for (int j = 0; j < (train_stops.second - train_stops.first); j++) {
            stations[train_stops.first + j]++;
        }

        trains[i] = train_stops;
    }
    int boardings = -1;
    if (stations[station_count-1] == 0) {
        cout << -1 << endl;
        return 0;
    }
    vector<int> boarded_trains(0, 0);
    pair<int, int> current_station (0, 0);
    while (current_station.second != station_count - 1) {
        if (stations[current_station.second] == 0) {
            cout << -1 << endl;
            return 0;
        }
        boardings++;
        current_station = get_longest(current_station, trains);
        boarded_trains.push_back(current_station.first);

    }
    cout << boardings << endl;
    for (int train : boarded_trains) {
        cout << train + 1 << " ";
    }
    cout << endl;



}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 2/50
1 Hibás válasz 0/0 3ms 1832 KiB
2 Hibás válasz 0/0 7ms 2872 KiB
3 Elfogadva 1/1 3ms 2260 KiB
4 Elfogadva 1/1 3ms 2476 KiB
5 Hibás válasz 0/2 3ms 2688 KiB
6 Hibás válasz 0/2 3ms 2772 KiB
7 Hibás válasz 0/2 3ms 2804 KiB
8 Hibás válasz 0/2 3ms 2812 KiB
9 Hibás válasz 0/2 3ms 2788 KiB
10 Hibás válasz 0/2 4ms 3088 KiB
11 Hibás válasz 0/2 4ms 3464 KiB
12 Hibás válasz 0/2 4ms 3632 KiB
13 Hibás válasz 0/2 3ms 3400 KiB
14 Hibás válasz 0/2 4ms 3756 KiB
15 Hibás válasz 0/2 4ms 3940 KiB
16 Hibás válasz 0/2 4ms 4200 KiB
17 Hibás válasz 0/2 4ms 4628 KiB
18 Hibás válasz 0/2 6ms 4716 KiB
19 Hibás válasz 0/2 6ms 4656 KiB
20 Hibás válasz 0/2 6ms 4656 KiB
21 Hibás válasz 0/2 7ms 4584 KiB
22 Hibás válasz 0/2 7ms 4844 KiB
23 Időlimit túllépés 0/2 259ms 3816 KiB
24 Időlimit túllépés 0/2 268ms 3944 KiB
25 Időlimit túllépés 0/2 268ms 4108 KiB
26 Időlimit túllépés 0/2 248ms 4088 KiB
27 Időlimit túllépés 0/2 264ms 4064 KiB
28 Időlimit túllépés 0/2 264ms 4104 KiB