146002025-01-20 13:07:41Leventusz09A lehető legkevesebb átszállás (50 pont)cpp17Wrong answer 36/50300ms1784 KiB
#include <iostream>
#include <vector>

using namespace std;

int main() {
	int N, M;
	cin >> N >> M;

	vector<int> ss(M, -1);
	vector<int> ls(M, -1);
	vector<int> ind(M, -1);

	for (int i = 0, a, b; i < N; i++) {
		cin >> a >> b;
		for (int j = a + 1; j <= b; j++) {
			if (ss[j - 1] < ss[j - 1] || ss[j - 1] == -1) {
				ss[j - 1] = ss[a - 1] + 1;
				ls[j - 1] = a - 1;
				ind[j - 1] = i;
			}
		}

		//cout << "LOG (ss):  "; for (int& j : ss) cout << j << "; "; cout << endl;
		//cout << "LOG (ls):  "; for (int& j : ls) cout << j << "; "; cout << endl;
		//cout << "LOG (ind): "; for (int& j :ind) cout << j << "; "; cout << endl;
	}
	if (ss[M - 1] == 0) {
		cout << -1;
		return 0;
	}
	cout << ss[M - 1] << "\n";
	vector<int> ol;
	for (int i = M - 1; i != 0; ) {
		if (i == -1) break;
		ol.push_back(ind[i] + 1);
		i = ls[i];
	}
	for (int i = ss[M - 1]; i >= 0; i--) cout << ol[i] << " ";
	cout << endl;

	return 0;
}
SubtaskSumTestVerdictTimeMemory
base36/50
1Accepted0/01ms316 KiB
2Accepted0/012ms1784 KiB
3Accepted1/11ms316 KiB
4Accepted1/11ms316 KiB
5Wrong answer0/21ms316 KiB
6Accepted2/21ms316 KiB
7Accepted2/22ms316 KiB
8Accepted2/22ms316 KiB
9Accepted2/23ms316 KiB
10Accepted2/24ms572 KiB
11Accepted2/24ms1012 KiB
12Accepted2/27ms824 KiB
13Accepted2/22ms760 KiB
14Accepted2/24ms820 KiB
15Accepted2/24ms820 KiB
16Accepted2/27ms1000 KiB
17Accepted2/28ms1424 KiB
18Accepted2/29ms1332 KiB
19Accepted2/210ms1492 KiB
20Accepted2/210ms1580 KiB
21Accepted2/212ms1584 KiB
22Accepted2/213ms1588 KiB
23Time limit exceeded0/2300ms1076 KiB
24Time limit exceeded0/2300ms1304 KiB
25Time limit exceeded0/2300ms1368 KiB
26Time limit exceeded0/2300ms1780 KiB
27Time limit exceeded0/2284ms1596 KiB
28Time limit exceeded0/2300ms1332 KiB