oj.uz

Submission #512600

# Submission time Handle Problem Language Result Execution time Memory
512600 2022-01-16T13:33:25 Z sidon Teams (CEOI11_tea) C++17
0 / 100
 360 ms 51264 KB 
#include <bits/stdc++.h>
using namespace std;

const int Z = 1e6+2, oo = 2e9;

int N, A[Z], S[Z];
array<int, 3> F[Z], DP[Z];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	cin >> N;

	for(int i = 1; i <= N; i++) {
		cin >> A[i];
		S[i] = i;
		F[i + 1] = {-oo};
	}

	sort(S, S + N + 1, [&](int i, int j) {
		return A[i] < A[j];
	});

	for(int i = 1; i <= N; i++) {
		DP[i] = {-oo};

		for(int j = i - A[S[i]] + 1; j >= 1; j -= j&-j)
			DP[i] = max(DP[i], F[j]);

		++DP[i][0];
		swap(DP[i][1], DP[i][2]);
		DP[i][1] = i;

		for(int j = i + 1; j <= N+1; j += j&-j) 
			F[j] = max(F[j], DP[i]);
	}

	vector<vector<int>> res = {{}};
	int curr = DP[N][2];

	for(int i = N + 1; --i; ) {
		if(curr == i) {
			res.push_back({});
			curr = DP[i][2];
		}
		res.back().push_back(S[i]);
	}

	cout << size(res) << '\n';
	for(auto &V : res) {
		cout << size(V);
		for(auto &i : V) cout << ' ' << i;
		cout << '\n';
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Incorrect 2 ms 524 KB Output isn't correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 4236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 4668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 285 ms 36188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 360 ms 48468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 320 ms 51264 KB Output isn't correct
2 Halted 0 ms 0 KB -