7530 | 2024. 01. 09 13:30:08 | gyjazmin | A lehető legkevesebb átszállás (50 pont) | cpp17 | Elfogadva 50/50 | 10ms | 5536 KiB |
#include <iostream>
#include <vector>
using namespace std;
vector<int> v(1);
vector<vector<int>> graf;
int cv = 0;
bool kovetk() {
v.push_back(0);
int eleje= cv;
int s = v.size()-1;
int i = v[s-1]+1;
int maxv=cv;
while (i <= graf.size() - 1&& graf[i][0] <= cv) {
if (graf[i][1] > maxv) {
maxv = graf[i][1];
v[s] = i;
}
i++;
}
cv = maxv;
if (eleje == cv) {
return false;
}
else {
return true;
}
}
int main()
{
int n,m;
cin >> n>>m;
graf.resize(n+1);
for (int i = 0;i < n;i++) {
int egyik, masik;
cin >> egyik >> masik;
graf[i].resize(2);
graf[i + 1].push_back(egyik);
graf[i + 1].push_back(masik);
if (egyik == 1&& masik >cv) {
cv = masik;
v[0] = i + 1;
}
}
if (cv == 0) {
cout << -1 << endl;
}
else {
bool eljut=true;
while (cv != m) {
eljut = kovetk();
if (!eljut) {
cout << -1 << endl;
break;
}
}
if (eljut) {
cout << v.size() - 1 << endl;
for (int i = 0;i < v.size();i++) {
cout << v[i] << " ";
}
cout << endl;
}
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1872 KiB | |||
2 | Elfogadva | 0/0 | 10ms | 3024 KiB | |||
3 | Elfogadva | 1/1 | 3ms | 2288 KiB | |||
4 | Elfogadva | 1/1 | 3ms | 2496 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2572 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 2720 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 3120 KiB | |||
8 | Elfogadva | 2/2 | 4ms | 3360 KiB | |||
9 | Elfogadva | 2/2 | 4ms | 3488 KiB | |||
10 | Elfogadva | 2/2 | 4ms | 3620 KiB | |||
11 | Elfogadva | 2/2 | 6ms | 3936 KiB | |||
12 | Elfogadva | 2/2 | 7ms | 4072 KiB | |||
13 | Elfogadva | 2/2 | 3ms | 3956 KiB | |||
14 | Elfogadva | 2/2 | 4ms | 4220 KiB | |||
15 | Elfogadva | 2/2 | 4ms | 4356 KiB | |||
16 | Elfogadva | 2/2 | 7ms | 4492 KiB | |||
17 | Elfogadva | 2/2 | 8ms | 4896 KiB | |||
18 | Elfogadva | 2/2 | 8ms | 4984 KiB | |||
19 | Elfogadva | 2/2 | 9ms | 4980 KiB | |||
20 | Elfogadva | 2/2 | 9ms | 5008 KiB | |||
21 | Elfogadva | 2/2 | 10ms | 5204 KiB | |||
22 | Elfogadva | 2/2 | 10ms | 5180 KiB | |||
23 | Elfogadva | 2/2 | 9ms | 5184 KiB | |||
24 | Elfogadva | 2/2 | 9ms | 5324 KiB | |||
25 | Elfogadva | 2/2 | 9ms | 5284 KiB | |||
26 | Elfogadva | 2/2 | 9ms | 5344 KiB | |||
27 | Elfogadva | 2/2 | 10ms | 5536 KiB | |||
28 | Elfogadva | 2/2 | 10ms | 5496 KiB |