Submission #206755

#	Time	Username	Problem	Language	Result	Execution time	Memory
206755		kshitij_sodani	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1179 ms	169584 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];
	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 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-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);
				}
			}
		}
	}

	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 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(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-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);
				}
			}
		}
	}

	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+1<=n-1){
					coo+=dp2[k-j][n-1-(i+1)];

				}
				else{
					if(j==k){
						coo+=1;
					}
				}
				if(coo==2){
					spp=0;
				}

			}
			if(spp==1){
				black[i]=1;

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

	}


	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(j>0){
				if(it[j-1]==2 or (white[j-1]==0 and it[j-1]==0)){
					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(coo==2){
				if(pos==0){
					l=j;
					dd.pb(j);
					r=j+c[i]-1;
					sta=j;
					las=r;
					pos=1;

				}
				else{

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

		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));
			}
			else{
				if(dd[jj]>ee[ee.size()-1].b){
					ee.pb(mp(dd[jj],dd[jj]+c[i]-1));
				}
				else{
					ee[ee.size()-1].b=dd[jj]+c[i]-1;
				}
			}
		}
		for(int jj=0;jj<ee.size();jj++){
			for(int kk=ee[jj].a;kk<ee[jj].b+1;kk++){
				black[kk]=1;
			}
		}

	}	
	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:339:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int jj=0;jj<dd.size();jj++){
                ~~^~~~~~~~~~
paint.cpp:354:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int jj=0;jj<ee.size();jj++){
                ~~^~~~~~~~~~
paint.cpp:266:7: warning: variable 'las' set but not used [-Wunused-but-set-variable]
   int las;
       ^~~
paint.cpp:267:7: warning: variable 'sta' set but not used [-Wunused-but-set-variable]
   int sta;
       ^~~
paint.cpp:366:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<pp.size();i++){
              ~^~~~~~~~~~
paint.cpp:142: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