Submission #135435

#	Time	Username	Problem	Language	Result	Execution time	Memory
135435		random0029	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1010 ms	103728 KiB

paint

// ItnoE
#include<bits/stdc++.h>
using namespace std;
const int N = 200005, K = 109;
int X[N], U[N], W[N], B[N], M[K][N];
bool dp[K][N];
string solve_puzzle(string S, vector < int > C)
{
	int n = (int)S.size();
	int k = (int)C.size();
	S = '.' + S;
	C.insert(C.begin(), 0);
	for (int i = 1; i <= n; i ++)
	{
		X[i] = X[i - 1] + (S[i] != '_');
		U[i] = U[i - 1] + (S[i] != 'X');
	}
	dp[0][0] = 1;
	for (int j = 0; j <= k; j ++)
		for (int i = 1; i <= n; i ++)
		{
			if (S[i] != 'X' && dp[j][i - 1])
				dp[j][i] = 1;
			if (j == 1 && i == C[j] && X[i] - X[i - C[j]] == C[j])
				dp[j][i] = 1;
			if (j && i > C[j] && X[i] - X[i - C[j]] == C[j] && S[i - C[j]] != 'X' && dp[j - 1][i - C[j] - 1])
				dp[j][i] = 1;
		}
	assert(dp[k][n]);
	queue < pair < int , int > > qu;
	qu.push({n, k});
	while (qu.size())
	{
		int i = qu.front().first;
		int j = qu.front().second;
		qu.pop();
		if (M[j][i]) continue;
		M[j][i] = 1;
		if (S[i] != 'X' && dp[j][i - 1])
			qu.push({i - 1, j}), W[i] ++, W[i + 1] --;
		if (j == 1 && i == C[j] && X[i] - X[i - C[j]] == C[j])
			B[1] ++, B[i + 1] --;
		if (j && i > C[j] && X[i] - X[i - C[j]] == C[j] && S[i - C[j]] != 'X' && dp[j - 1][i - C[j] - 1])
			qu.push({i - C[j] - 1, j - 1}), B[i - C[j] + 1] ++, B[i + 1] --, W[i - C[j]] ++, W[i - C[j] + 1] --;
	}
	string R = "";
	for (int i = 1; i <= n; i ++)
	{
		W[i] += W[i - 1];
		B[i] += B[i - 1];
		if (W[i] && !B[i])
			R += '_';
		else if (B[i] && !W[i])
			R += 'X';
		else
			R += '?';
	}
	return (R);
}
/*int main()
{
	string S = ".X........";
	S = "";
	for (int i = 0; i < 20000; i ++)
		S += ".";
	vector < int > C = {1, 1, 1, 1, 1, 1, 1, 1};
	string R = solve_puzzle(S, C);
	cout << R << endl;
}*/

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10