4401 2023. 03. 27 15:40:52 kdb A lehető legkevesebb átszállás (50 pont) cpp17 Elfogadva 50/50 4ms 5080 KiB
#include <iostream>
#include <vector>
using namespace std;

struct Train
{
    int start;
    int end;
};

ostream& operator<<(ostream& os, const vector<int>& input)
{
    for (const int i : input) os << i << " ";
    return os;
}

int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    vector<Train>vec(n + 1);

    for (size_t i = 1; i < n + 1; i++)
    {
        int a, b;
        cin >> a >> b;
        vec[i] = { a, b };
    }
    vector<int>ans;
    int i = 1, covered = 1;
    while (covered < m)
    {
        int best = -1;
        while (i <= n and vec[i].start <= covered)
        {
            if (best == -1 or vec[best].end < vec[i].end) best = i;
            i++;

        }
        if (best == -1)
        {
            cout << -1 << "\n";
            return 0;
        }
        else
        {
            covered = vec[best].end;
            ans.push_back(best);
        }
    }
    cout << ans.size() - 1 << "\n" << ans << "\n";
}
/*
6 9
1 2
1 4
2 6
3 4
6 9
7 9


*/
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1828 KiB
2 Elfogadva 0/0 4ms 2268 KiB
3 Elfogadva 1/1 3ms 2264 KiB
4 Elfogadva 1/1 2ms 2348 KiB
5 Elfogadva 2/2 3ms 2484 KiB
6 Elfogadva 2/2 3ms 2696 KiB
7 Elfogadva 2/2 3ms 2920 KiB
8 Elfogadva 2/2 3ms 3092 KiB
9 Elfogadva 2/2 3ms 3440 KiB
10 Elfogadva 2/2 3ms 3404 KiB
11 Elfogadva 2/2 3ms 3672 KiB
12 Elfogadva 2/2 4ms 3632 KiB
13 Elfogadva 2/2 3ms 3872 KiB
14 Elfogadva 2/2 3ms 4140 KiB
15 Elfogadva 2/2 3ms 4128 KiB
16 Elfogadva 2/2 4ms 4456 KiB
17 Elfogadva 2/2 4ms 4592 KiB
18 Elfogadva 2/2 4ms 4648 KiB
19 Elfogadva 2/2 4ms 4840 KiB
20 Elfogadva 2/2 4ms 4812 KiB
21 Elfogadva 2/2 4ms 4816 KiB
22 Elfogadva 2/2 4ms 4808 KiB
23 Elfogadva 2/2 4ms 4808 KiB
24 Elfogadva 2/2 4ms 4804 KiB
25 Elfogadva 2/2 4ms 4808 KiB
26 Elfogadva 2/2 4ms 4948 KiB
27 Elfogadva 2/2 4ms 4948 KiB
28 Elfogadva 2/2 4ms 5080 KiB