Submission #779104

#	Time	Username	Problem	Language	Result	Execution time	Memory
779104		vjudge1	Paint By Numbers (IOI16_paint)	C++17	0 / 100	1 ms	468 KiB

paint

#include<bits/stdc++.h> 
#include "paint.h"
using namespace std;
const int N=5e3+37;
int dp[N][N][2], dp2[N][N][2];
int check1[N];

void check(string s, vector<int> c){
	int p=0;
	int k=c.size(); int n= s.size();

	for(auto i: c){
		p+=i;
		check1[p] = 1;
	}

	if(s[0]!='X') dp[0][0][0] = 1;
	if(s[0] != '_') dp[0][1][1] = 1;


	for(int i=1; i<n; i++){
		for(int l=0; l<n; l++){
			if(dp[i-1][l][0]){
				if(s[i]!='X') dp[i][l][0] = 1;
				if(s[i]!='_') dp[i][l+1][1] = 1;
			}
			if(dp[i-1][l][1]){
				if(check1[l]&&s[i]!='X') dp[i][l][0] = 1;
				else if(s[i]!='_') dp[i][l+1][1] = 1;
			}
		}
	}

	for(int i=0; i<=n; i++) check1[i]=0;

	int f=0;
	p++;
	for(int l=k-1; l>=0; l--){
		f+=c[l];

		check1[p-f] = 1;

	}
	p--;
	//cout<<p;
	if(s[n-1]!='X') dp2[n-1][p][0] = 1;
	if(s[n-1] != '_') dp2[n-1][p][1] = 1;

	for(int i=n-2; i>=0; i--){
		for(int l=0; l<=n; l++){
			if(dp2[i+1][l][0]){
				if(s[i]!='X') dp2[i][l][0] = 1;
				if(s[i]!='_') dp2[i][l][1] = 1;
			}
			if(dp2[i+1][l][1]){
				if(check1[l]&&s[i]!='X'){
				 	
				 	dp2[i][l-1][0]=1;
				 	
				 }
				else if(s[i]!='_') dp2[i][l-1][1] = 1;
			}
		}
	}


}	
std::string solve_puzzle(std::string s, std::vector<int> c) {
   
	string t, ans;
	int n=s.size();
	int k=c.size();
	check(s, c);

	ans=s;
	for(int i=0; i<=n; i++) check1[i] =0;
	check1[c[0]] = 1;
	check1[0] = 1;
	for(int i=1; i<c.size(); i++){
		c[i]+=c[i-1];
	}
	for(int i=0; i<n; i++){
		if(s[i]!='.') continue;

		int b=0, w=0;
		for(int l=0; l<n; l++){

			if(dp[i][l][1] && dp2[i][l][1])
			{
				b = 1;
			}
			if(dp[i][l][0] && dp2[i][l][0]){
				w = 1;
			}
		}

		if(b&&w) ans[i] = '?';
		else if(b) ans[i] ='X';
		else if(w) ans[i]='_';

	}
	//cout<<ans;
	return ans;
}	

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for(int i=1; i<c.size(); i++){
      |               ~^~~~~~~~~
paint.cpp:72:6: warning: unused variable 'k' [-Wunused-variable]
   72 |  int k=c.size();
      |      ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10