Submission #779137

#	Time	Username	Problem	Language	Result	Execution time	Memory
779137		vjudge1	Paint By Numbers (IOI16_paint)	C++17	0 / 100	1 ms	340 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;
	}
	for(int i=0; i<=n; i++){
		for(int l=0; l<=n; l++){
			for(int j=0; j<2; j++){
				dp2[i][l][j]=dp[i][l][j]=0;
			}
		}
		check1[i]=0;
	}
	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++){
		if(s[i]!='.') continue;
		s[i]='X';
		check(s, c);
				int b=0, w=0;

		if(dp2[0][0][0]||dp2[0][1][1]) b=1;
		s[i]='_'; check(s, c);
		if(dp2[0][0][0]||dp2[0][1][1]) w=1;
		
		/*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;
}	

/*
int main() {

    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif

    string s; cin >> s;

     int c_len;
    assert(1 == scanf("%d", &c_len));
    std::vector<int> c(c_len);
    for (int i = 0; i < c_len; i++) {
        assert(1 == scanf("%d", &c[i]));
    }
   std::string ans = solve_puzzle(s, c);

    // BEGIN SECRET
 //   puts("098d134608c94f7413faac591054ee35");
    // END SECRET

   // printf("%s\n", ans.data());
    return 0;
}*/

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:79:6: warning: unused variable 'k' [-Wunused-variable]
   79 |  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