40832023-03-13 08:59:16tamasmarkA lehető legkevesebb átszállás (50 pont)cpp17Runtime error 48/5068ms64780 KiB
// legkevesebb atszallas.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>

using namespace std;

struct adat
{
    long long kezd, veg;
};
vector<adat>x;
vector<int >megold;
int i, j, n, m, maxi,a,b;

int main()
{
    cin >> m >> n;
    x.resize(m + 1);
    for (i = 1; i <= m; ++i)
    {
        cin >> x[i].kezd >> x[i].veg;
    }
    i = 1;
    maxi = 0;
    while (i <= n && x[i].kezd == 1)
    {
        if (x[i].veg >= x[maxi].veg) maxi = i;
        ++i;
    }
    megold.push_back(maxi);
    i = maxi;
    while (i <= m && x[i].veg < n)
    {
        j = i;
        maxi = 0;
        while (j <= m && x[j].kezd <= x[i].veg)
        {
            if (x[j].veg >= x[maxi].veg)
            {
                maxi = j;
            }
            j++;
        }
        if (maxi == 0)
        {
            cout << -1;
            return 0;
        }
        else
        {
            megold.push_back(maxi);
            i = maxi;
        }
    }
    cout << megold.size()-1 << "\n";
    for (auto& e : megold) cout << e << " ";
    return 0;
}
/*
6 9
1 2
1 4
2 6
3 4
6 9
7 9
*/
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file
SubtaskSumTestVerdictTimeMemory
base48/50
1Accepted0/03ms1900 KiB
2Accepted0/08ms2464 KiB
3Runtime error0/168ms64780 KiB
4Runtime error0/167ms64524 KiB
5Accepted2/23ms2668 KiB
6Accepted2/22ms2756 KiB
7Accepted2/23ms2772 KiB
8Accepted2/24ms2888 KiB
9Accepted2/24ms3100 KiB
10Accepted2/24ms3196 KiB
11Accepted2/24ms3484 KiB
12Accepted2/26ms3684 KiB
13Accepted2/23ms3444 KiB
14Accepted2/24ms3584 KiB
15Accepted2/24ms3612 KiB
16Accepted2/26ms3900 KiB
17Accepted2/27ms4220 KiB
18Accepted2/28ms4244 KiB
19Accepted2/28ms4164 KiB
20Accepted2/28ms4292 KiB
21Accepted2/28ms4516 KiB
22Accepted2/28ms4512 KiB
23Accepted2/28ms4504 KiB
24Accepted2/28ms4636 KiB
25Accepted2/28ms4704 KiB
26Accepted2/28ms4764 KiB
27Accepted2/28ms4764 KiB
28Accepted2/28ms4840 KiB