Submission #367642

#	Time	Username	Problem	Language	Result	Execution time	Memory
367642		mosiashvililuka	Paint By Numbers (IOI16_paint)	C++14	100 / 100	411 ms	243760 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,k,dp[200003][103],dp2[200003][103],kl[200003][103],l[103];
string s,h;
vector <int> C;
std::string solve_puzzle(std::string sss, std::vector<int> CC) {
	a=sss.size();k=CC.size();
	C.push_back(0);
	for(j=0; j<CC.size(); j++){
		C.push_back(CC[j]);
	}
	C.push_back(0);
	s="."+sss+"....";
	for(i=0; i<=a+1; i++){
		if(s[i]=='X') break;
		dp[i][0]=1;
		//dp2[i][k+1]=1;
	}
	for(i=a+1; i>=1; i--){
		if(s[i]=='X') break;
		dp2[i][k+1]=1;
	}
	c=-3;// "_"
	d=-3;// "X"
	dp[0][0]=1;
	for(i=1; i<=a; i++){
		if(s[i]=='_') c=i;
		if(s[i]=='X') d=i;
		for(j=1; j<=k; j++){
			if(s[i]=='_'){
				dp[i][j]=dp[i-1][j];
				continue;
			}
			if(s[i]=='.'&&dp[i-1][j]==1){
				dp[i][j]=1;
				continue;
			}
/*			if(dp[i-1][j]==1){
				dp[i][j]=1;
				continue;
			}*/
			if(i<C[j]) continue;
			if(c>=i-C[j]+1) continue;
			if(s[i-C[j]]=='X') continue;
			if(j==1){
				//dp[i][j]=1;
				dp[i][j]=dp[i-C[j]][j-1];
			}else{
				if(i>C[j]){
					dp[i][j]=dp[i-C[j]-1][j-1];
				}
			}
		}
	}
	/*for(i=1; i<=a; i++){
		cout<<dp[i][0]<<" ";
	}
	cout<<endl;
	for(i=1; i<=a; i++){
		cout<<dp[i][1]<<" ";
	}
	cout<<endl;*/
	//exit(0);
	c=a+3;// "_"
	d=a+3;// "X"
	dp2[a+1][k+1]=1;
	for(i=a; i>=1; i--){
		if(s[i]=='_') c=i;
		if(s[i]=='X') d=i;
		for(j=k; j>=1; j--){
			if(s[i]=='_'){
				dp2[i][j]=dp2[i+1][j];
				continue;
			}
			if(s[i]=='.'&&dp2[i+1][j]==1){
				dp2[i][j]=1;
				continue;
			}
/*			if(dp2[i+1][j]==1){
				dp2[i][j]=1;
				continue;
			}*/
			if(a-i+1<C[j]) continue;
			if(j==k){
				if(i+C[j]-1>=c) continue;
				//dp2[i][j]=1;
				dp2[i][j]=dp2[i+C[j]][j+1];
			}else{
				if(a-i+1<=C[j]) continue;
				if(i+C[j]-1>=c) continue;
				if(s[i+C[j]]=='X') continue;
				dp2[i][j]=dp2[i+C[j]+1][j+1];
			}
		}
	}
/*	for(i=1; i<=a; i++){
		cout<<dp2[i][1]<<" ";
	}
	cout<<endl;
	for(i=1; i<=a; i++){
		cout<<dp2[i][2]<<" ";
	}
	cout<<endl;*/
	//exit(0);
	c=a+3;// "_"
	d=a+3;// "X"
	for(i=a; i>=1; i--){
		if(s[i]=='_') c=i;
		if(s[i]=='X') d=i;
		for(j=1; j<=k; j++){
			if(i+C[j]-1>a) continue;
			if(i+C[j]-1>=c) continue;
			if(j!=k){
				if(i+C[j]>a) continue;
				if(s[i+C[j]]=='X') continue;
				if(dp2[i+C[j]+1][j+1]==0) continue;
			}else{
				if(dp2[i+C[j]][j+1]==0) continue;
			}
			if(j!=1){
				if(i<=2) continue;
				if(s[i-1]=='X') continue;
				if(dp[i-2][j-1]==0) continue;
			}else{
				if(dp[i-1][j-1]==0) continue;
			}
			kl[i][j]=1;
		}
	}
	/*for(i=1; i<=a; i++){
		cout<<kl[i][0]<<" ";
	}
	cout<<endl;
	for(i=1; i<=a; i++){
		cout<<kl[i][1]<<" ";
	}
	cout<<endl;*/
	for(i=0; i<=k+1; i++){
		l[i]=-a-2;
	}
	for(i=1; i<=a; i++){
		//zx - "_"
		//xc - "X"
		zx=0;xc=0;
		for(j=0; j<=k; j++){
			if(kl[i][j]==1) l[j]=i;
		}
		if(s[i]!='.'){
			h.push_back(s[i]);
			continue;
		}
		for(j=0; j<=k; j++){
			if(dp[i-1][j]==1&&dp2[i+1][j+1]==1){
				zx=1;
				break;
			}
		}
		for(j=0; j<=k; j++){
			if(i-C[j]+1<=l[j]){
				xc=1;
				break;
			}
		}
		if(zx==1&&xc==1){
			h.push_back('?');
		}else{
			if(zx==1){
				h.push_back('_');
			}else{
				h.push_back('X');
			}
		}
	}
	return h;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:10:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for(j=0; j<CC.size(); j++){
      |           ~^~~~~~~~~~

• 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