Submission #344774

#	Time	Username	Problem	Language	Result	Execution time	Memory
344774		Kerim	Paint By Numbers (IOI16_paint)	C++17	100 / 100	297 ms	44328 KiB

paint

#include "paint.h"
#include "bits/stdc++.h"
#define MAXN 200009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int n,k;
int arr[MAXN],par[MAXN],white[MAXN],black[MAXN],arap[MAXN];
string s;
const int K=103;
bool pre[K][MAXN],suf[K][MAXN];
string solve_puzzle(string tmp,vector<int> c) {
	s="#"+tmp+"#";n=int(tmp.size());k=int(c.size());
	for(int i=1;i<=k;i++)arr[i]=c[i-1];
	for(int i=1;i<=n;i++)par[i]=par[i-1]+(s[i]=='_');//count white
	for(int i=1;i<=n+1;i++)arap[i]=arap[i-1]+(s[i]=='X');//count black
	if(k==1){
		int mx=0,mn=n+1,p=1;
		for(int i=1;i+arr[1]<=n+1;i++)
			if(par[arr[1]+i-1]==par[i-1] and !arap[i-1] and arap[n+1]==arap[i+arr[1]-1]){
				while(p<arr[1]+i){
					if(p>=i)	
						black[p]=1;
					p++;	
				}
				umax(mx,i-1);
				umin(mn,arr[1]+i);
			}		
		for(int i=1;i<=mx;i++)
			white[i]=1;
		for(int i=mn;i<=n;i++)
			white[i]=1;
	}
	else{
		pre[0][0]=1;
		for(int i=0;i<=k;i++){
			for(int j=1;j<=n;j++){
				if(s[j]!='X')
					pre[i][j]=pre[i][j-1];
				else
					pre[i][j]=0;
				if(i and j>=arr[i] and par[j]==par[j-arr[i]] and s[j-arr[i]]!='X'){
					if(i==1)
						pre[i][j]|=pre[i-1][j-arr[i]];
					else if(j>arr[i])
						pre[i][j]|=pre[i-1][j-arr[i]-1];
				}
			}
		}
		suf[k+1][n+1]=1;
		for(int i=k+1;i>=1;i--){
			for(int j=n;j>=1;j--){
				if(s[j]!='X')
					suf[i][j]=suf[i][j+1];
				else
					suf[i][j]=0;
				if(i<=k and j+arr[i]<=n+1 and par[j-1]==par[j+arr[i]-1] and s[j+arr[i]]!='X'){
					if(i==k)
						suf[i][j]|=suf[i+1][j+arr[i]];
					else if(j+arr[i]<=n)
						suf[i][j]|=suf[i+1][j+arr[i]+1];
				}
			}
		}
		/*
		for(int i=0;i<=k;i++){
			for(int j=0;j<=n;j++)
				printf("dp[%d][%d] = %d\n",i,j,suf[i][j]);
			wr
		}
		*/
		for(int i=1;i<=n;i++)
			if(s[i]=='.'){
				white[i]=0;
				for(int j=0;j<=k;j++)
					white[i]|=(pre[j][i-1] and suf[j+1][i+1]);
			}
		for(int i=1;i<=k;i++)
			for(int j=1;j+arr[i]<=n+1;j++){
				if(i==1){
					if(j+arr[i]<=n and par[j+arr[i]-1]==par[j-1] and pre[i-1][j-1] and suf[i+1][j+arr[i]+1] and s[j+arr[i]]!='X'){
						for(int h=j;h<j+arr[i];h++){
							black[h]=1;
						}
					}	
				}
				else if(i==k){
					if(j>=2 and par[j+arr[i]-1]==par[j-1] and pre[i-1][j-2] and suf[i+1][j+arr[i]] and s[j-1]!='X'){
						for(int h=j;h<j+arr[i];h++){
							black[h]=1;
						}
					}
				}
				else{
					if(j>=2 and j+arr[i]<=n and par[j+arr[i]-1]==par[j-1] and pre[i-1][j-2] and suf[i+1][j+arr[i]+1]
						and s[j+arr[i]]!='X' and s[j-1]!='X'){
						for(int h=j;h<j+arr[i];h++){
							black[h]=1;
						}
					}	
				}
				
			}
	}
	for(int i=0;i<n;i++)	
		if(tmp[i]=='.'){
			if(black[i+1] and white[i+1])	
				tmp[i]='?';
			else if(black[i+1])
				tmp[i]='X';
			else
				tmp[i]='_';
		}
	return tmp;
}

• 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