| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 609757 | gonzakia29 | Paint By Numbers (IOI16_paint) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "paint.h"
#include <vector>
#include <string>
#include <iostream>
#include <cassert>
const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];
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(int i, int j){
int v1 = 0, v2 = 0;
if (i == N){
if (j < K){
return 0;
} else{
puede_[i] = true;
return 1;
}
}
if (j<K && N-i < C[j]){
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;
}
return 1;
} else{
return 0;
}
}
if (dp(i+1,j)&& S[i] != 'X'){
v1 = 1;
puede_[i] = true;
}
if (i == 0){
if (S[i+C[j]] != 'X' && blanks[i+C[j]-1] == 0){
if(dp(i+C[j]+1,j+1)&&S[i] != '_'){
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;
}
}
}
return v1|v2;
}
string solve_puzzle(string s, vector<int> c) {
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;
}