Submission #552643

#	Time	Username	Problem	Language	Result	Execution time	Memory
552643		Hanksburger	Paint By Numbers (IOI16_paint)	C++17	100 / 100	326 ms	43740 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
bool dp[105][200005], dp2[105][200005], b[200005], w[200005];
int black[200005], white[200005], diff[200005], d[105];
string ans;
string solve_puzzle(string s, vector<int> c)
{
	int n=s.length(), k=c.size(), sum=0;
	s.insert(s.begin(), '0');
	s.insert(s.end(), '0');
	c.insert(c.begin(), 0);
	c.insert(c.end(), 0);
	if (n==c[1])
	{
		for (int i=1; i<=n; i++)
			ans.push_back('X');
		return ans;
	}
    for (int i=1; i<=n; i++)
    {
    	black[i]=black[i-1]+(s[i]=='X');
    	white[i]=white[i-1]+(s[i]=='_');
	}
	for (int i=1; i<=k; i++)
		d[i]=d[i-1]+c[i];
	dp[0][0]=1;
	for (int i=1; i<=n; i++)
		dp[0][i]=(!black[i]);
	for (int i=1; i<=k; i++)
	{
		for (int j=d[i]+i-1; j<=n; j++)
		{
			if (s[j]!='X')
				dp[i][j]|=dp[i][j-1];
			if (s[j]!='_')
			{
				if (j==c[i])
				{
					if (!(white[j]))
						dp[i][j]=1;
				}
				else
				{
					if (!(white[j]-white[j-c[i]]) && s[j-c[i]]!='X')
						dp[i][j]|=dp[i-1][j-c[i]-1];
				}
			}
		}
	}
	dp2[k+1][n+1]=1;
	for (int i=n; i>=1; i--)
		dp2[k+1][i]=(!(black[n]-black[i-1]));
	for (int i=k; i>=1; i--)
	{
		for (int j=n-(d[k]-d[i-1]+k-i)+1; j>=1; j--)
		{
			if (s[j]!='X')
				dp2[i][j]|=dp2[i][j+1];
			if (s[j]!='_')
			{
				if (j==n-c[i]+1)
				{
					if (!(white[n]-white[j-1]))
						dp2[i][j]=1;
				}
				else
				{
					if (!(white[j+c[i]-1]-white[j-1]) && s[j+c[i]]!='X')
						dp2[i][j]|=dp2[i+1][j+c[i]+1];
				}
			}
		}
	}
	for (int i=1; i<=k; i++)
	{
		for (int j=1; j<=n-c[i]+1; j++)
		{
			if (s[j-1]!='X' && s[j+c[i]]!='X' && !(white[j+c[i]-1]-white[j-1]))
			{
				if (j==1)
				{
					if (i==1 && dp2[2][c[i]+2])
					{
						diff[j]++;
						diff[j+c[i]]--;
					}
				}
				else if (j==n-c[i]+1)
				{
					if (dp[k-1][j-2] && i==k)
					{
						diff[j]++;
						diff[j+c[i]]--;
					}
				}
				else
				{
					if (dp[i-1][j-2] && dp2[i+1][j+c[i]+1])
					{
						diff[j]++;
						diff[j+c[i]]--;
					}
				}
			}
		}
	}
	for (int i=1; i<=n; i++)
	{
		sum+=diff[i];
		b[i]=sum;
	}
	for (int i=1; i<=n; i++)
	{
		if (s[i]=='X')
			continue;
		for (int j=0; j<=k; j++)
		{
			if (dp[j][i-1] && dp2[j+1][i+1])
			{
				w[i]=1;
				break;
			}
		}
	}
	for (int i=1; i<=n; i++)
	{
		if (b[i] && w[i])
			ans.push_back('?');
		else if (b[i])
			ans.push_back('X');
		else
			ans.push_back('_');
	}
	return ans;
}

• 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