| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 103054 | Osama_Alkhodairy | 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 <bits/stdc++.h>
#include "grader.cpp"
//#include "paint.h"
using namespace std;
const int N = 200005;
const int K = 105;
int n, k, w[N];
bool dp[N][K][2];
string s;
vector <int> c;
int get_sum(int l, int r){
return w[r] - w[l - 1];
}
bool checkW(int idx){
for(int j = 0 ; j <= k ; j++){
if((j == 0 || dp[idx - 1][j][0]) && (j == k || dp[idx + 1][j + 1][1])){
return 1;
}
}
return 0;
}
std::string solve_puzzle(std::string S, std::vector<int> C) {
s = S;
c = C;
n = s.size();
k = c.size();
c.insert(c.begin(), -1);
s = ';' + s;
for(int i = 1 ; i <= n ; i++)
w[i] = w[i - 1] + (s[i] == '_');
dp[0][0][0] = 1;
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= k ; j++){
dp[i][j][0] = dp[i - 1][j][0];
dp[i][j][0] |= (i - c[j] + 1 >= 1) && (get_sum(i - c[j] + 1, i) == 0) && (dp[max(0, i - c[j] - 1)][j - 1][0]);
}
}
dp[n + 1][k + 1][1] = 1;
for(int i = n ; i >= 1 ; i--){
for(int j = k ; j >= 1 ; j--){
dp[i][j][1] = dp[i + 1][j][1];
dp[i][j][1] |= (i + c[j] - 1 <= n) && (get_sum(i, i + c[j] - 1) == 0) && (dp[min(n + 1, i + c[j] + 1)][j + 1][1]);
}
}
vector <int> canB(n + 5);
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= k ; j++){
if(dp[i][j][0] && (get_sum(i - c[j] + 1, i) == 0) && dp[max(0, i - c[j] - 1)][j - 1][0] && (j == k || dp[i + 2][j + 1][1])){
canB[i - c[j] + 1]++;
canB[i + 1]--;
}
}
}
for(int i = 1 ; i <= n ; i++)
canB[i] += canB[i - 1];
string ret = "";
for(int i = 1 ; i <= n ; i++){
if(s[i] == 'X' || s[i] == '_'){
ret += s[i];
continue;
}
int cur = 0;
if(checkW(i)) cur |= 1;
if(canB[i] > 0) cur |= 2;
if(cur == 1) ret += '_';
else if(cur == 2) ret += 'X';
else ret += '?';
}
return ret;
}