oj.uz

Submission #512970

# Submission time Handle Problem Language Result Execution time Memory
512970 2022-01-16T20:32:37 Z sidon Teams (CEOI11_tea) C++17
100 / 100
 1297 ms 83656 KB 
#include <bits/stdc++.h>
using namespace std;

const int Z = 1e6+1;
 
int N, P[Z];
array<int, 2> A[Z], DP[Z];
 
int build(int x) {
	priority_queue<array<int, 2>> b;
	b.push(DP[0]);
 
 	for(int i = 1, r = 0; i <= N; i++) {
		int R = max(-1, i - A[i][0]);
 
		while(r < R) b.push(DP[++r]);
		r = R;
 
		while(!empty(b) && (b.top()[1] < i - x || b.top()[1] > R)) b.pop();
 
		if(empty(b)) DP[i] = {-(int)2e9, -1};
		else {
			DP[i] = b.top();
			P[i] = DP[i][1];
			DP[i] = {DP[i][0] + 1, i};
		}
	}
	return DP[N][0];
}

int main() {
	cin >> N;

	for(int i = 1; i <= N; i++)
		cin >> A[A[i][1] = i][0];

	sort(A, A + N + 1);
 
	int best = build(1e6), sz = N;
 
	for(int j=1<<20; j/=2; ) {
		if(sz - j < A[N][0]) continue;
		if(build(sz - j) == best) sz -= j;
	}
	build(sz);
 
	int curr = P[N];
 
	vector<vector<int>> res = {{}};
 
	for(int i = N + 1; --i; ) {
		if(curr == i) {
			res.push_back({});
			curr = P[curr];
		}
		res.back().push_back(A[i][1]);
	}
 
	cout << size(res) << '\n';
	for(auto &V : res) {
		cout << size(V);
		for(auto &i : V) cout << ' ' << i;
		cout << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 460 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 4 ms 460 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 2820 KB Output is correct
2 Correct 61 ms 3512 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 3668 KB Output is correct
2 Correct 72 ms 3368 KB Output is correct
3 Correct 69 ms 3668 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 28996 KB Output is correct
2 Correct 730 ms 29056 KB Output is correct
3 Correct 857 ms 28596 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1297 ms 34920 KB Output is correct
2 Correct 991 ms 83656 KB Output is correct
3 Correct 1111 ms 36076 KB Output is correct
4 Correct 813 ms 32348 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 919 ms 32332 KB Output is correct
2 Correct 444 ms 26796 KB Output is correct
3 Correct 1169 ms 35880 KB Output is correct
4 Correct 1228 ms 35356 KB Output is correct