Submission #328209

#	Time	Username	Problem	Language	Result	Execution time	Memory
328209		keta_tsimakuridze	Paint By Numbers (IOI16_paint)	C++14	100 / 100	336 ms	168420 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,K=105;
int dp1[N][K],dp2[N][K],i,mx[N],ans[N][2],j,a[N],k,n;
string Ans;
#include <cstdlib>
 
std::string solve_puzzle(std::string s, std::vector<int> c) {
 
	n=s.size()+1;
	k=c.size();
	s="##"+s;
	s+="##";
	for(i=1;i<=k;i++){
		a[i]=c[i-1];
	}
	i=0;
	while(i<=n && s[i]!='X') dp1[i][0]=1,i++;
	i=n+2;
	while(i>=0 && s[i]!='X') dp2[i][k+1]=1,i--;
	for(i=2;i<=n;i++){
		mx[i]=mx[i-1];
		if(s[i]=='_') mx[i]=i;
		for(j=1;j<=k;j++){
			if(a[j]+1>i) break;
			if(mx[i]<=i-a[j] && s[i-a[j]]!='X' &&  dp1[i-a[j]-1][j-1]){
					dp1[i][j]=1;
			}
			 if(s[i]!='X') dp1[i][j]=max(dp1[i-1][j],dp1[i][j]);
		 
		}
	}
	mx[n+1]=n+2;
	for(i=n;i>=2;i--){
		mx[i]=mx[i+1];
		if(s[i]=='_') mx[i]=i;
		for(j=k;j>=1;j--){
			if(a[j]>n-i+1) break;
			if(mx[i]>=i+a[j] && s[i+a[j]]!='X' &&  dp2[i+a[j]+1][j+1] ){
					dp2[i][j]=1;
			}
			 if(s[i]!='X') dp2[i][j]=max(dp2[i+1][j],dp2[i][j]);
		}
	}
	i=0;
	
	for(i=2;i<=n;i++){
		
		for(j=1;j<=k+1;j++){
			 if(s[i]!='X')if(dp1[i-1][j-1] && dp2[i+1][j]){
				ans[i-1][0]=1;  //cout<<i<<endl;
			}
			 if(s[i]!='_')
			 if(i+a[j]<=n+2 && dp2[i][j] && s[i-1]!='X' && dp1[i-2][j-1] && mx[i]>=i+a[j] && s[i+a[j]]!='X' && dp2[i+a[j]+1][j+1]){
			 
			 	ans[i-1][1]++;
			 	ans[i+a[j]-1][1]--;//cout<<i<<"__"<<i+a[j]<<" "<<ans[i-1][1]<<endl;
			 }
		}
		
	}
	for(i=1;i<n;i++){
		ans[i][1]+=ans[i-1][1];
		if(ans[i][0] && ans[i][1]) Ans+='?';
		else if(ans[i][0]) Ans+='_';
		else Ans+='X';
	}
	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