oj.uz

답안 #552904

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
552904 2022-04-24T09:33:31 Z blue Teams (CEOI11_tea) C++17
100 / 100
 384 ms 108628 KB 
#include <iostream>
#include <vector>
using namespace std;

using vi = vector<int>;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	cin >> N;

	vi lst[1+N];
	for(int i = 1; i <= N; i++)
	{
		int a;
		cin >> a;
		lst[a].push_back(i);
	}

	vi A(1, 0);
	vi I(1, 0);
	for(int i = N; i >= 1; i--)
	{
		for(int x : lst[i])
		{
			A.push_back(i);
			I.push_back(x);
		}
	}

	vi maxteams(1+N);
	vi sizelim(1+N, 5'000'000);

	maxteams[0] = sizelim[0] = 0;

	vi occ[1+N+1];

	if(A[1] + 1 <= N+1)
		occ[A[1] + 1].push_back(1);

	for(int i = A[1]+1; i <= N; i++)
	{
		if(A[i] + i <= N+1)
			occ[A[i] + i].push_back(i);
	}

	for(int i = A[1]; i <= N; i++)
	{
		// cerr << "i = " << i << '\n';
		// if(i < A[1])
		// {
		// 	maxteams[i] = sizelim[i] = prev[i] = -1;
		// 	continue;
		// }

		maxteams[i] = 0;


		for(int j : occ[i+1])
		{
			if(j > i) continue;

			if(maxteams[j-1] != maxteams[i-1]) continue;

			int currsize = max(sizelim[j-1], i-j+1);
			if(maxteams[i] == 0 || sizelim[i] > currsize)
			{
				maxteams[i] = maxteams[i-1] + 1;
				sizelim[i] = currsize;
			}
		}

		// cerr << "phase 1 : " << maxteams[i] << '\n';

		if(maxteams[i] == 0)
		{
			maxteams[i] = maxteams[i-1];

			if(maxteams[i-1] * sizelim[i-1] == i-1)
			{
				sizelim[i] = sizelim[i-1] + 1;
			}
			else
			{
				sizelim[i] = sizelim[i-1];
			}



			// for(int j = 1; j <= i; j++) if(A[j] <= i-j+1)
			for(int j : occ[i+1])
			{
				// if(A[j] > i-j+1) continue;
				if(j > i) continue;

				if(maxteams[j-1] != maxteams[i] - 1) continue;

				int currsize = max(sizelim[j-1], i-j+1);
				if(sizelim[i] > currsize)
				{
					sizelim[i] = currsize;
				}
			}
		}
	}

	// for(int i = 1; i <= N; i++) cerr << A[i] << ' ' << I[i] << " : " << maxteams[i] << ' ' << sizelim[i] << '\n';


	int ci = N;

	cout << maxteams[N] << '\n';
	for(int z = 1; z <= maxteams[N]; z++)
	{
		int pci = 0;
		for(int i = max(A[1], ci - min(sizelim[N], sizelim[ci])); i < ci; i++)
		{
			// cerr << "ci = " << ci << '\n';
			// cerr << i << ' ' << (sizelim[pci] <= sizelim[N]) << ' ' << maxteams[i] << ' ' << maxteams[ci] << '\n';
			if(sizelim[i] <= sizelim[N] && maxteams[i] == maxteams[ci] - 1 && A[i+1] <= ci - i)
			{
				pci = i;
				break;
			}
		}

		// cerr << ci << " -> " << pci << '\n';

		// cerr << "ci = " << ci << '\n';
		cout << ci - pci << ' ';
		for(int q = pci+1; q <= ci; q++)
			cout << I[q] << ' ';
		cout << '\n';

		ci = pci;
	}
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 852 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 7544 KB Output is correct
2 Correct 22 ms 8748 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 9024 KB Output is correct
2 Correct 28 ms 8232 KB Output is correct
3 Correct 22 ms 9056 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 211 ms 79820 KB Output is correct
2 Correct 185 ms 79308 KB Output is correct
3 Correct 187 ms 79908 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 253 ms 101380 KB Output is correct
2 Correct 334 ms 108160 KB Output is correct
3 Correct 253 ms 108628 KB Output is correct
4 Correct 329 ms 96496 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 221 ms 78624 KB Output is correct
2 Correct 219 ms 73928 KB Output is correct
3 Correct 258 ms 106356 KB Output is correct
4 Correct 384 ms 102048 KB Output is correct