76802024-01-10 12:43:32adamA lehető legkevesebb átszállás (50 pont)cpp17Időlimit túllépés 12/50300ms63464 KiB
#include <bits/stdc++.h>
using namespace std;

pair<int, int> get_longest (pair<int, int> from, vector<pair<int, int>> trains, vector<vector<int>> stations) {
    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() {
    int train_count = 0;
    int station_count = 0;
    cin >> train_count >> station_count;
    vector<pair<int, int>> trains(train_count, pair(0, 0));
    vector<vector<int>> stations(station_count, vector(0, 0));


    for (int i = 0; i < train_count -1; 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 - 1 + j].push_back(i);
        }

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

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



}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base12/50
1Elfogadva0/03ms1808 KiB
2Időlimit túllépés0/0259ms32376 KiB
3Időlimit túllépés0/1261ms5844 KiB
4Időlimit túllépés0/1261ms10144 KiB
5Elfogadva2/23ms2804 KiB
6Időlimit túllépés0/2300ms10352 KiB
7Elfogadva2/217ms8536 KiB
8Elfogadva2/217ms10716 KiB
9Elfogadva2/227ms13144 KiB
10Elfogadva2/274ms18824 KiB
11Időlimit túllépés0/2272ms14568 KiB
12Időlimit túllépés0/2282ms17600 KiB
13Elfogadva2/2105ms10592 KiB
14Időlimit túllépés0/2263ms9972 KiB
15Időlimit túllépés0/2270ms13364 KiB
16Időlimit túllépés0/2257ms17888 KiB
17Időlimit túllépés0/2246ms25952 KiB
18Időlimit túllépés0/2263ms27816 KiB
19Időlimit túllépés0/2270ms30268 KiB
20Időlimit túllépés0/2238ms31456 KiB
21Futási hiba0/272ms63464 KiB
22Futási hiba0/271ms63448 KiB
23Futási hiba0/2101ms63424 KiB
24Futási hiba0/2116ms63392 KiB
25Futási hiba0/2126ms63352 KiB
26Futási hiba0/2135ms63352 KiB
27Futási hiba0/2143ms63320 KiB
28Futási hiba0/2143ms63316 KiB