Submission #546007

#	Time	Username	Problem	Language	Result	Execution time	Memory
546007		adamjinwei	Paint By Numbers (IOI16_paint)	C++14	100 / 100	593 ms	43408 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
#define inf 1000000007
#define mod 1000000007
// #define int long long
// #pragma GCC optimize("Ofast","inline","-ffast-math")
// #pragma GCC target("avx,sse2,sse3,sse4,mmx")
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) x=-x,putchar('-');
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n,k;
char s[300005];
int c[105];
int sumb[200005],sumw[200005];
bool dpf[105][200005],dpb[105][200005];
bool canb[200005],canw[200005],canst[200005];
bool check(int l,int r,int op)
{
	if(l<1||r>n) return false;
	if(op!=1&&l-1>=1&&s[l-1]=='X') return false;
	if(op!=0&&r+1<=n&&s[r+1]=='X') return false;
	if(sumw[r]-sumw[l-1]>0) return false;
	return true;
}
string solve_puzzle(string S,vector<int> C)
{
	n=S.size(),k=C.size();
	for(int i=1;i<=n;++i) s[i]=S[i-1];
	for(int i=1;i<=k;++i) c[i]=C[i-1];
	for(int i=1;i<=n;++i) sumb[i]=sumb[i-1]+(s[i]=='X'),sumw[i]=sumw[i-1]+(s[i]=='_');
	for(int i=0;i<=k;++i)
		for(int j=0;j<=n;++j)
		{
			if(!i) dpf[i][j]=(!sumb[j]);
			else if(!j) dpf[i][j]=0;
			else if(s[j]=='_') dpf[i][j]=dpf[i][j-1];
			else if(s[j]=='X') dpf[i][j]=(check(j-c[i]+1,j,0)&&dpf[i-1][max(0,j-c[i]-1)]);
			else dpf[i][j]=(dpf[i][j-1]||(check(j-c[i]+1,j,0)&&dpf[i-1][max(0,j-c[i]-1)]));
		}
	for(int i=k+1;i>=1;--i)
		for(int j=n+1;j>=1;--j)
		{
			if(i==k+1) dpb[i][j]=(!(sumb[n]-sumb[j-1]));
			else if(j==n+1) dpb[i][j]=0;
			else if(s[j]=='_') dpb[i][j]=dpb[i][j+1];
			else if(s[j]=='X') dpb[i][j]=(check(j,j+c[i]-1,1)&&dpb[i+1][min(n+1,j+c[i]+1)]);
			else dpb[i][j]=(dpb[i][j+1]||(check(j,j+c[i]-1,1)&&dpb[i+1][min(n+1,j+c[i]+1)]));
		}
	for(int i=1;i<=n;++i)
	{
		if(s[i]=='X') continue;
		for(int j=0;j<=k;++j)
			canw[i]|=(dpf[j][i-1]&&dpb[j+1][i+1]);
	}
	for(int i=1;i<=k;++i)
	{
		for(int j=1;j<=n;++j)
			canst[j]=(check(j,j+c[i]-1,2)&&dpf[i-1][max(0,j-2)]&&dpb[i+1][min(n+1,j+c[i]+1)]);
		int cur=0;
		for(int j=1;j<=n;++j)
		{
			cur+=canst[j];if(j-c[i]>=1) cur-=canst[j-c[i]];
			canb[j]|=(cur>0);
		}
	}
	string ans;
	for(int i=1;i<=n;++i)
		if(canb[i]&&canw[i]) ans+="?";
		else if(canb[i]) ans+="X";
		else ans+="_";
	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