Submission #442302

#	Time	Username	Problem	Language	Result	Execution time	Memory
442302		adamjinwei	Paint By Numbers (IOI16_paint)	C++14	80 / 100	2084 ms	988 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
#define inf 1000000007
#define mod 1000000007
//#define int long long
using namespace std;
template<typename T> void read(T &x)
{
	x=0;char ch=getchar();int fh=1;
	while(ch<'0'||ch>'9') {if(ch=='-') fh=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	x*=fh;
}
template<typename T> void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<typename T> void writeln(T x)
{
	write(x);
	puts("");
}
int n,m;
char s[200005];
int c[105];
int sumx[200005],sumb[200005];
bool dp[200005][105];
char res[200005];
string solve_puzzle(string S,vector<int> C)
{
	n=S.size()+1;
	m=C.size();
	for(int i=1;i<=n;++i)
	{
		if(i!=n)
			s[i]=S[i-1];
		else s[i]='_';
	}
	for(int i=1;i<=m;++i)
		c[i]=C[i-1];
	for(int i=1;i<=n;++i)
		if(s[i]!='.')
			res[i]=s[i];
		else
		{
			s[i]='X';
			for(int j=1;j<=n;++j)
			{
				sumx[j]=sumx[j-1]+(s[j]=='X'?1:0);
				sumb[j]=sumb[j-1]+(s[j]=='_'?1:0);
			}
			dp[0][0]=1;
			for(int j=1;j<=n;++j)
				for(int k=0;k<=m;++k)
				{
					dp[j][k]=0;
					if(dp[j-1][k]&&sumx[j]-sumx[j-1]==0) dp[j][k]=1;
					if(k&&j>=c[k]+1&&sumb[j-1]-sumb[j-c[k]-1]==0&&sumx[j]-sumx[j-1]==0&&dp[j-c[k]-1][k-1])
						dp[j][k]=1;
				}
			bool isx=dp[n][m];
			s[i]='_';
			for(int j=1;j<=n;++j)
			{
				sumx[j]=sumx[j-1]+(s[j]=='X'?1:0);
				sumb[j]=sumb[j-1]+(s[j]=='_'?1:0);
			}
			dp[0][0]=1;
			for(int j=1;j<=n;++j)
				for(int k=0;k<=m;++k)
				{
					dp[j][k]=0;
					if(dp[j-1][k]&&sumx[j]-sumx[j-1]==0) dp[j][k]=1;
					if(k&&j>=c[k]+1&&sumb[j-1]-sumb[j-c[k]-1]==0&&sumx[j]-sumx[j-1]==0&&dp[j-c[k]-1][k-1])
						dp[j][k]=1;
				}
			bool isb=dp[n][m];
			if(isx&&isb) res[i]='?';
			if(isx&&!isb) res[i]='X';
			if(!isx&&isb) res[i]='_';
			s[i]='.';
		}
	string ans;
	for(int i=1;i<n;++i)
		ans+=res[i];
	return ans;
}
// signed main()
// {
// 	// vector<int> vec;
// 	// vec.push_back(3);
// 	// // vec.push_back(4);
// 	// solve_puzzle(".X......",vec);
// 	return 0;
// }

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