Submission #647908

#	Time	Username	Problem	Language	Result	Execution time	Memory
647908		jamezzz	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1563 ms	159424 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pf printf
#define pb push_back
#define all(x) x.begin(),x.end()
#define lb(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define ub(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define INF 1023456789
typedef pair<int,int> ii;

#define maxk 105
#define maxn 200005

int far[maxn],pfx[maxk][maxn],sfx[maxk][maxn];
vector<ii> black,white;

inline bool canblack(int l,int r){
	int i=lb(black,ii(l,INF));
	if(i==0)return false;
	return r<=black[i-1].se;
}

inline bool canwhite(int l,int r){
	int i=lb(white,ii(l,INF));
	if(i==0)return false;
	return r<=white[i-1].se;
}

string solve_puzzle(string s,vector<int> c){
	int n=s.length(),k=c.size();
	string ans(n,'.');
	
	int l=-1,r=-1;
	for(int i=0;i<n;++i){
		if(s[i]=='_'){
			if(r!=-1)black.pb({l+1,r+1});
			l=r=-1;
		}
		else{
			if(l==-1)l=r=i;
			else r=i;
		}
	}
	if(r!=-1)black.pb({l+1,r+1});
	
	l=r=-1;
	for(int i=0;i<n;++i){
		if(s[i]=='X'){
			if(r!=-1)white.pb({l+1,r+1});
			l=r=-1;
		}
		else{
			if(l==-1)l=r=i;
			else r=i;
		}
	}
	if(r!=-1)white.pb({l+1,r+1});

	pfx[0][0]=1;
	for(int i=1;i<=n;++i){
		if(s[i-1]=='X')break;
		pfx[0][i]=1;
	}
	for(int i=1;i<=k;++i){
		for(int j=1;j<=n;++j){
			if(s[j-1]!='X')pfx[i][j]|=pfx[i][j-1];//can be white
			if(s[j-1]!='_'){//can be black
				if(j-c[i-1]<0)continue;
				if(j-c[i-1]!=0&&s[j-c[i-1]-1]=='X')continue;//j-c[i] is white
				if(!canblack(j-c[i-1]+1,j))continue;//[j-c[i]+1,j] can black
				if(i==k&&j+c[i-1]<=n&&!canwhite(j+c[i-1],n))continue;
				if(i!=1||j-c[i-1]!=0)pfx[i][j]|=pfx[i-1][j-c[i-1]-1];
				else pfx[i][j]=1;
			}
		}
	}
	sfx[k+1][n+2]=sfx[k+1][n+1]=1;
	for(int i=n;i>=1;--i){
		if(s[i-1]=='X')break;
		sfx[k+1][i]=1;
	}
	for(int i=k;i>=1;--i){
		for(int j=n;j>=1;--j){
			if(s[j-1]!='X')sfx[i][j]|=sfx[i][j+1];//can be white
			if(s[j-1]!='_'){//can be black
				if(j+c[i-1]-1>n)continue;
				if(j+c[i-1]-1!=n&&s[j+c[i-1]-1]=='X')continue;//j+c[i] is white
				if(!canblack(j,j+c[i-1]-1))continue;//[j,j+c[i]-1] can black
				if(i==1&&j!=1&&!canwhite(1,j-1))continue;
				sfx[i][j]|=sfx[i+1][j+c[i-1]+1];
			}
		}
	}
	
	for(int j=1;j<=n;++j){
		if(s[j-1]=='X')continue;
		for(int i=0;i<=k;++i){
			if(pfx[i][j-1]&&sfx[i+1][j+1])ans[j-1]='_';
		}
	}
	
	int far=0;
	for(int j=1;j<=n;++j){
		for(int i=1;i<=k;++i){
			if(!(i==1&&j==1)&&(j==1||s[j-2]=='X'))continue;
			if(j+c[i-1]<=n&&s[j+c[i-1]-1]=='X')continue;
			if(j+c[i-1]-1>n||!canblack(j,j+c[i-1]-1))continue;
			if(((i==1&&j==1)||pfx[i-1][j-2])&&sfx[i+1][j+c[i-1]+1]){
				int l=far,r=j+c[i-1]-1;
				for(int i=l+1;i<=r;++i){
					if(ans[i-1]=='_')ans[i-1]='?';
					else if(ans[i-1]=='.')ans[i-1]='X';
				}
				far=r;
			}
		}
		far=max(far,j);
	}
	
	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