45302023-03-29 12:50:58TomaSajtA lehető legkevesebb átszállás (50 pont)cpp17Elfogadva 50/504ms4620 KiB
#include <bits/stdc++.h>
using namespace std;
#define speed cin.tie(0); ios::sync_with_stdio(0)

struct line {
    int s, e, id;
};

int main() {
    speed;
    int n, m; cin >> n >> m;
    vector<line> lines(n);
    for (int j = 0; j < n; j++) {
        cin >> lines[j].s >> lines[j].e;
        lines[j].id = j + 1;
    }
    int loc = 1;
    int i = 0;
    vector<int> sol;
    while (loc < m && i < n) {
        int bestI = -1;
        while (i < n && lines[i].s <= loc) {
            int bestE = bestI == -1 ? -1 : lines[bestI].e;
            if (lines[i].e > bestE) bestI = i;
            i++;
        }
        if (bestI == -1) break;
        loc = lines[bestI].e;
        sol.push_back(lines[bestI].id);
    }
    if (loc != m) {
        cout << "-1";
    }
    else {
        cout << sol.size() - 1 << '\n';
        for (auto j : sol) cout << j << ' ';
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms1828 KiB
2Elfogadva0/04ms2272 KiB
3Elfogadva1/13ms2228 KiB
4Elfogadva1/13ms2440 KiB
5Elfogadva2/23ms2800 KiB
6Elfogadva2/22ms2748 KiB
7Elfogadva2/23ms2892 KiB
8Elfogadva2/23ms3236 KiB
9Elfogadva2/23ms3348 KiB
10Elfogadva2/23ms3304 KiB
11Elfogadva2/23ms3424 KiB
12Elfogadva2/24ms3532 KiB
13Elfogadva2/23ms3500 KiB
14Elfogadva2/23ms3512 KiB
15Elfogadva2/23ms3848 KiB
16Elfogadva2/24ms3764 KiB
17Elfogadva2/24ms3908 KiB
18Elfogadva2/24ms4192 KiB
19Elfogadva2/24ms4284 KiB
20Elfogadva2/24ms4288 KiB
21Elfogadva2/24ms4296 KiB
22Elfogadva2/24ms4532 KiB
23Elfogadva2/24ms4504 KiB
24Elfogadva2/24ms4504 KiB
25Elfogadva2/24ms4620 KiB
26Elfogadva2/24ms4504 KiB
27Elfogadva2/24ms4512 KiB
28Elfogadva2/24ms4508 KiB