Submission #206754

#	Time	Username	Problem	Language	Result	Execution time	Memory
206754		kshitij_sodani	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1176 ms	169576 KiB

paint

#include <iostream>
#include <bits/stdc++.h>
#include <paint.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long llo;
#define a first
#define  b second
#define endl "\n"
string solve_puzzle(string s,vector<int> c){
	int k=c.size();
	int n=s.size();
	char ss[n];
	strcpy(ss,s.c_str());
	int it[n];
	for(int i=0;i<n;i++){
		if(ss[i]=='.'){
			it[i]=0;
		}
		else if(ss[i]=='_'){
			it[i]=1;
		}
		else{
			it[i]=2;
		}
	}
	char ans[n];
	for(int i=0;i<n;i++){
		ans[i]=ss[i];
		if(ans[i]=='.'){
			ans[i]='?';
		}
	}
	int dp[k+1][n];
	//cout<<n<<endl;
	memset(dp,0,sizeof(dp));
	for(int i=0;i<n;i++){
		if(it[i]==2){
			break;
		}
		dp[0][i]=1;
	}
	int back[n];
	int so=0;
	int ind5;

	for(int i=0;i<n;i++){
		if(it[i]!=1){
			if(so==1){
				back[i]=ind5;
			}
			else{
				back[i]=i;
				ind5=i;
				so=1;
			}
		}
		else{
			so=0;
		}
	}
	for(int i=0;i<n;i++){
		if(it[i]==1){
			//cout<<"-1 ";
		}
		else{
			//cout<<back[i]<<" ";
		}

	}
	//cout<<endl;
	for(int kk=1;kk<k+1;kk++){
		for(int i=0;i<n;i++){
			if(it[i]==1){
				if(i>0){
					dp[kk][i]=dp[kk][i-1];
				}
			}
			else if(it[i]==2){
				if(i>=c[kk-1]-1){
				
					if(back[i]>i-c[kk-1]+1){
							continue;
						}
					if(i-c[kk-1]>=0){
						if(it[i-c[kk-1]]==2){
							continue;
						}
					}
					if(i-c[kk-1]-1>=0){
						dp[kk][i]=dp[kk-1][i-c[kk-1]-1];
					}
					else{
						if(kk==1){
							dp[kk][i]=1;
						}
					}
				}			
			}
			else{	
				if(i>=c[kk-1]-1){
					int sp=1;

					if(back[i]>i-c[kk-1]+1 and sp){
							sp=0;
						}
					if(i-c[kk-1]>=0 and sp){
						if(it[i-c[kk-1]]==2 and sp){
							sp=0;
						}
					}
					/*if(i==2 and kk==1){
						//cout<<sp<<endl;
					}*/
					if(i-c[kk-1]-1>=0 and sp){
						dp[kk][i]=dp[kk-1][i-c[kk-1]-1];
					}
					else{
						if(kk==1 and sp==1){
							dp[kk][i]=1;
						}
					}
				}	
				if(i>0){
					dp[kk][i]=min(dp[kk][i]+dp[kk][i-1],1);
				}
			}
		}
	}
/*	for(int i=0;i<k+1;i++){
		for(int j=0;j<n;j++){
			cout<<dp[i][j]<<" ";
		}
		cout<<endl;
	}*/
	int tt[n];
	for(int i=0;i<n;i++){
		tt[i]=it[n-i-1];
	}
	int dp2[k+1][n];
    int cc[k];
	for(int i=0;i<k;i++){
		cc[i]=c[k-i-1];
	}
	memset(dp2,0,sizeof(dp2));
	for(int i=0;i<n;i++){
		if(tt[i]==2){
			break;
		}
		dp2[0][i]=1;
	}
	int back2[n];
	int soo=0;

	for(int i=0;i<n;i++){
		if(tt[i]!=1){
			if(soo==1){
				back2[i]=ind5;
			}
			else{
				back2[i]=i;
				ind5=i;
				soo=1;
			}
		}
		else{
			soo=0;
		}
	}
	for(int i=0;i<n;i++){
		if(tt[i]==1){
			//cout<<"-1 ";
		}
		else{
			//cout<<back2[i]<<" ";
		}

	}
	//cout<<endl;
	for(int kk=1;kk<k+1;kk++){
		for(int i=0;i<n;i++){
			if(tt[i]==1){
				if(i>0){
					dp2[kk][i]=dp2[kk][i-1];
				}
			}
			else if(tt[i]==2){
				if(i>=cc[kk-1]-1){
					
					if(back2[i]>i-cc[kk-1]+1){
							continue;
						}
					if(i-cc[kk-1]>=0){
						if(tt[i-cc[kk-1]]==2){
							continue;
						}
					}
					if(i-cc[kk-1]-1>=0){
						dp2[kk][i]=dp2[kk-1][i-cc[kk-1]-1];
					}
					else{
						if(kk==1){
							dp2[kk][i]=1;
						}
					}
				}			
			}
			else{	
				if(i>=cc[kk-1]-1){
					int sp=1;
					/*if(kk>1 and sp){
						if(tt[i-1]==1){
							//continue;
							sp=0;
						}
						
					}*/
					if(back2[i]>i-cc[kk-1]+1 and sp){
							sp=0;
						}
					if(i-cc[kk-1]>=0 and sp){
						if(tt[i-cc[kk-1]]==2 and sp){
							sp=0;
						}
					}
					/*if(i==2 and kk==1){
						//cout<<sp<<endl;
					}*/
					if(i-cc[kk-1]-1>=0 and sp){
						dp2[kk][i]=dp2[kk-1][i-cc[kk-1]-1];
					}
					else{
						if(kk==1 and sp==1){
							dp2[kk][i]=1;
						}
					}
				}	
				if(i>0){
					dp2[kk][i]=min(dp2[kk][i]+dp2[kk][i-1],1);
				}
			}
		}
	}

/*	for(int i=0;i<k+1;i++){
		for(int j=0;j<n;j++){
			cout<<dp2[i][j]<<" ";
		}
		cout<<endl;
	}*/
	////cout<<dp2[1][]
	int white[n];
	memset(white,0,sizeof(white));
		int black[n];
	memset(black,0,sizeof(black));
	for(int i=0;i<n;i++){
		if(it[i]==0){
			int spp=1;
			for(int j=0;j<k+1;j++){
				int coo=0;
				if(it[i]==2){
					continue;
				}
				if(i>0){
					coo+=dp[j][i-1];
				}
				else if(j==0){
					coo+=1;
				}
				/*if(i==5 and j==1){
					cout<<coo<<endl;
				}*/
			/*	if(i==3 and j==1){
					//cout<<coo<<',';
				}*/
				if(i+1<=n-1){
					coo+=dp2[k-j][n-1-(i+1)];
				/*	if(i==3 and j==1){
						//cout<<n-1-(i+1)<<" "<<k-j<<",";
					}*/
				}
				else{
					if(j==k){
						coo+=1;
					}
				}
				if(coo==2){
					spp=0;
				}
			/*	if(i==3 and j==1){
					//cout<<coo<<','<<endl;
				}*/
			}
			if(spp==1){
				//cout<<i<<":";
				//it[i]=2;
				black[i]=1;

			}
			else{
				white[i]=1;
			}
		}

	}
	//cout<<endl<<endl;
	for(int i=0;i<n;i++){
		//cout<<it[i]<<" ";
	}
/*		for(int i=0;i<n;i++){
		cout<<white[i]<<",,";
	}
	cout<<endl;*/
	//cout<<endl<<endl;
	//cout<<endl;
	int vis[n];

	memset(vis,0,sizeof(vis));
	vector<int> pp;

	for(int i=0;i<k;i++){
		int pos=0;
		int l,r;
		vector<int> dd;
		int las;
		int sta;

		for(int j=0;j<n-c[i]+1;j++){
			if(j+c[i]<n){
				if(it[j+c[i]]==2 or (white[j+c[i]]==0 and it[j+c[i]]==0)){
					continue;
				}			
			}
			
			if(back[j+c[i]-1]>j or it[j+c[i]-1]==1){
				continue;
			}
		/*	if(i==0 and j==6){
				cout<<"oo"<<endl;
			}*/
			if(j>0){
				if(it[j-1]==2 or (white[j-1]==0 and it[j-1]==0)){
				/*	if(i==0 and j==6){
						cout<<"oo "<<it[j-1]<<" "<<white[j-1]<<" "<<endl;
					}*/
					continue;
				}
			}

		/*	if(i==0 and j==6){
				cout<<"oo"<<endl;
			}*/
/*
			if(j+c[i]<n){
				if(it[j+c[i]]==2){
					continue;
				}
			}*/

			int coo=0;
			
			if(j-2>=0){
				if(dp[i][j-2]){
					coo+=1;
				}
			}
			

			else{
				if(i==0){
					coo+=1;
				}
			}
		/*	if(i==0 and j==6){
				cout<<"ooo "<<coo<<endl;
			}*/
		
			if(n-1-(1+j+c[i])>=0){
				if(dp2[k-i-1][n-1-(1+j+c[i])]){
					coo+=1;
				}
			}
			else{
				if(k-i-1==0){
					coo+=1;
				}
			}
		/*	if(i==0 and j==6){
				cout<<"ooo "<<coo<<endl;
			}*/
			/*if(i==0 and j==0){
				cout<<"000 "<<coo<<" 000"<<endl;
			}*/
			if(coo==2){
				if(pos==0){
			//		cout<<i<<" "<<j<<endl;
					/*if(i==0){
					for(int hh=0;hh<j;hh++){
							if(it[hh]==0){
								dd.pb(hh);
							}
						}
					}
*/
					l=j;
					dd.pb(j);
					r=j+c[i]-1;
					sta=j;
					las=r;
					pos=1;

				}
				else{
			//		cout<<i<<" "<<j<<endl;
					/*if(j>r){
						for(int hh=las+1;hh<j;hh++){
							if(it[hh]==0){
								dd.pb(hh);

							}
						}
					}*/
					dd.pb(j);
					l=max(l,j);
					las=j+c[i]-1;
					r=min(r,j+c[i]-1);
				}
			}
			
		}

		/*if(pos){
		//	//cout<<l<<" "<<r<<endl;
			for(int i=l;i<r+1;i++){
				it[i]=2;
				//vis[i]=1;
			}
		}*/
		/*for(int i=0;i<dd.size();i++){
			//cout<<dd[i]<<"::";
		}*/
		//cout<<endl;
	/*	for(int hh=las+1;hh<n;hh++){
				if(it[hh]==0){
					dd.pb(hh);
				}
		}*/
		/*for(int jj=0;jj<dd.size();jj++){
			cout<<dd[jj]<<":";
		}
		cout<<i<<",,,"<<c[i]<<endl;*/
		int ll,rr;
		vector<pair<int,int>> ee;
		for(int jj=0;jj<dd.size();jj++){
			if(jj==0){
				ll=dd[jj];
				rr=dd[jj]+c[i]-1;
				ee.pb(mp(ll,rr));
			//	cout<<ll<<","<<rr<<endl;
			}
			else{
				if(dd[jj]>ee[ee.size()-1].b){
					ee.pb(mp(dd[jj],dd[jj]+c[i]-1));
				}
				else{
			//		cout<<dd[jj]+cc[i]-1<<"   "<<dd[jj]<<endl;
					ee[ee.size()-1].b=dd[jj]+c[i]-1;
				}
			}
		}
		for(int jj=0;jj<ee.size();jj++){
	//		cout<<ee[jj].a<<",,,"<<ee[jj].b<<endl;
			for(int kk=ee[jj].a;kk<ee[jj].b+1;kk++){
				black[kk]=1;
			}
		}
		/*ind5=0;
		for(int j=sta;j<n;j++){
			while(ind5<dd.size() and dd[ind5]<j){
				ind5+=1;
			}
		//	//cout<<j<<" , "<<ind5<<" "<<dd[ind5]<<endl;
			if(ind5<dd.size() and dd[ind5]==j){
				ind5+=1;
				continue;
			}
			else{
		//		//cout<<j<<",:,"<<endl;
				black[j]=1;
			}
		}*/
		////cout<<endl;
	}	
	string ans2="";
/*	for(int i=0;i<n;i++){
		cout<<black[i]<<",,";
	}
	cout<<endl;*/
	for(int i=0;i<pp.size();i++){
		if(it[pp[i]]==0){
			//cout<<pp[i]<<" ";
			it[pp[i]]=1;
		}
	}
	for(int i=0;i<n;i++){
		if(it[i]==0){
			if(white[i] and black[i]){
				ans2+="?";
			}
			else if(white[i]){
				ans2+="_";
			}
			else{
				ans2+="X";
			}
		}
		else if(it[i]==1){
			ans2+="_";
		}
		else{
			ans2+="X";
		}
	}
	return ans2;

}
/*int main(){
	vector<int> bb={2,3};
	cout<<"..._._...."<<endl;
//	cout<<solve_puzzle(".X........", {3})<<endl;
	cout<<solve_puzzle("..._._....", {3})<<endl;
	cout<<solve_puzzle("........", {3, 4})<<endl;

	cout<<solve_puzzle("..........", {3, 4})<<endl;
	cout<<"X......"<<endl;
	cout<<solve_puzzle("X......", {2,3})<<endl;
	
	cout<<solve_puzzle(".X._.._...", {2,3})<<endl;


	return 0;
}*/

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:455:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int jj=0;jj<dd.size();jj++){
                ~~^~~~~~~~~~
paint.cpp:472:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int jj=0;jj<ee.size();jj++){
                ~~^~~~~~~~~~
paint.cpp:326:7: warning: variable 'las' set but not used [-Wunused-but-set-variable]
   int las;
       ^~~
paint.cpp:327:7: warning: variable 'sta' set but not used [-Wunused-but-set-variable]
   int sta;
       ^~~
paint.cpp:500:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<pp.size();i++){
              ~^~~~~~~~~~
paint.cpp:159:13: warning: 'ind5' may be used uninitialized in this function [-Wmaybe-uninitialized]
     back2[i]=ind5;
     ~~~~~~~~^~~~~

• 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