Submission #609789

#	Time	Username	Problem	Language	Result	Execution time	Memory
609789		gonzakia29	Paint By Numbers (IOI16_paint)	C++17	100 / 100	769 ms	105516 KiB

paint

#include <bits/stdc++.h>
#include <cassert>


using namespace std;

int N, K;
string S;
vector <int> C;
bool puede_[200010];
bool puedeX[200010];
int blanks[200010];
int exes[200010];
int DP[200010][110];

int dp(int i, int j){
    if (DP[i][j] != -1){
        return DP[i][j];
    } else {
        
    	int v1 = 0, v2 = 0;
    	if (i == N){
    		if (j < K){
    		    DP[i][j] = 0;
    		    return 0;
    		} else{
    		    DP[i][j] = 1;
    		    return 1;
    		}
    	}
    	if (j<K && N-i < C[j]){
    	    DP[i][j] = 0;
    	    return 0;
    	}
    	if (j == K){
    		if (exes[N-1]==exes[i-1]){
    		    puede_[i] = true;
    		    for (int x = i; x < N; ++x){
    		        puede_[x] = true;
    		    }
    		    DP[i][j] = 1;
    			return 1;
    		} else{
    		    DP[i][j] = 0;
    			return 0;
    		}
    	}
    	if (S[i] != 'X' && dp(i+1,j)){
    		v1 = 1;
    		puede_[i] = true;
    	}
    	if (i == 0){
    		if (S[i+C[j]] != 'X' && blanks[i+C[j]-1] == 0){
    			if(S[i] != '_'&&dp(i+C[j]+1,j+1)){
    				v2 = 1;
    				puedeX[i] = true;
    				puede_[i+C[j]] = true;
    				for (int x = 0; x < C[j]; ++x){
    				    puedeX[i+x] = true;
    				}
    			}
    		}
    	} else if ((S[i+C[j]] != 'X' || i+C[j] >= N) && blanks[i+C[j]-1] == blanks[i-1]){
    		if(dp(i+C[j]+1,j+1)){
    			v2 = 1;
    			puedeX[i] = true;
    			puede_[i+C[j]] = true;
    			for (int x = 0; x < C[j]; ++x){
    			   puedeX[i+x] = true;
    			}
    		}
    	}
    	DP[i][j] = v1|v2;
    	return v1|v2;
    }
}

string solve_puzzle(string s, vector<int> c) {
    memset(DP, -1, sizeof(DP));
	string salida = "";
	s+="_";
	int n = s.size();
	int k = c.size();
	
	N = n;
	K = k;
	S = s;
	C = c;
	int counter = 0;
	for (int i = 0; i < N; ++i){
		if (s[i] == '_'){
			counter++;
		}
		blanks[i] = counter;
	}
	counter = 0;
	for (int i = 0; i < N; ++i){
		if (s[i] == 'X'){
			counter++;
		}
		exes[i] = counter;
	}
	dp(0,0);
	for (int i = 0; i < N-1; ++i){
		if (puedeX[i] == true){
			if (puede_[i] == true){
				salida += '?';
			} else{
				salida += 'X';
			}
		} else{
			salida += '_';
		}
	}
	
    return salida;
}

• 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