Submission #135457

#	Time	Username	Problem	Language	Result	Execution time	Memory
135457		Mahdi_Jfri	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1320 ms	121588 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 20;
const int maxk = 1e2 + 20;

string s;
int dp[maxn][maxk];

int c[maxk] , nw[maxn] , can[maxn][2];

bool visited[maxn][maxk];

// 0 -> white

void dfs(int n , int k)
{
	if(n <= 0 || !dp[n][k] || visited[n][k])
		return;
	visited[n][k] = 1;

	if(s[n] == 'X')
	{
		can[n - c[k - 1]][0]++;
		can[n - c[k - 1] + 1][0]--;
		can[n - c[k - 1] + 1][1]++;
		can[n + 1][1]--;

		dfs(n - c[k - 1] - 1 , k - 1);
	}
	else if(s[n] == '_')
	{
		can[n][0]++;
		can[n + 1][0]--;

		dfs(n - 1 , k);
	}
	else
	{
		int cnt = 0;
		if(k && n >= c[k - 1] && nw[n] - nw[n - c[k - 1]] == 0 && s[n - c[k - 1]] != 'X')
		{
			bool is = (n == c[k - 1]? k == 1 : dp[n - c[k - 1] - 1][k - 1] != 0);
			if(is)
			{
				can[n - c[k - 1]][0]++;
				can[n - c[k - 1] + 1][0]--;
				can[n - c[k - 1] + 1][1]++;
				can[n + 1][1]--;

				dfs(n - c[k - 1] - 1 , k - 1);
			}
		}
		if(dp[n - 1][k] != 0)
		{
			cnt++;
			can[n][0]++;
			can[n + 1][0]--;

			dfs(n - 1 , k);
		}
	}
}

string solve_puzzle(string S, vector<int> C)
{
	s = S;
	int n = s.size() , k = C.size();
	for(int i = 0; i < k; i++)
		c[i] = C[i];

	s = '_' + s;
	for(int i = 1; i <= n; i++)
		nw[i] = nw[i - 1] + (s[i] == '_');

	dp[0][0] = 1;
	for(int i = 1; i <= n; i++)
		for(int j = 0; j <= k; j++)
		{
			if(s[i] == 'X')
			{
				if(j && i >= c[j - 1] && nw[i] - nw[i - c[j - 1]] == 0 && s[i - c[j - 1]] != 'X')
					dp[i][j] = (i == c[j - 1]? j == 1 : dp[i - c[j - 1] - 1][j - 1] != 0);
			}
			else if(s[i] == '_')
				dp[i][j] = (dp[i - 1][j] != 0);
			else
			{
				if(j && i >= c[j - 1] && nw[i] - nw[i - c[j - 1]] == 0 && s[i - c[j - 1]] != 'X')
					dp[i][j] += (i == c[j - 1]? j == 1 : dp[i - c[j - 1] - 1][j - 1] != 0);
				dp[i][j] += (dp[i - 1][j] != 0);
			}
		}

	dfs(n , k);

	string res;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 0; j < 2; j++)
			can[i][j] += can[i - 1][j];

		if(!can[i][0] && !can[i][1])
			res += '?';
		else if(can[i][0] && can[i][1])
			res += '?';
		else if(can[i][0])
			res += '_';
		else
			res += 'X';
	}
	return res;
}

• 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