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 <bits/stdc++.h>
#define sz(x) int((x).size())
using namespace std;
#define MAXN 200010
#define MAXK 110
int lBeli[MAXN], rBeli[MAXN], b[MAXN], c[MAXN];
bool dpLK[MAXK][MAXN], dpRK[MAXK][MAXN], dpL[MAXK][MAXN], dpR[MAXK][MAXN];
std::string solve_puzzle(std::string s, std::vector<int> C) {
s = "%" + s + "%";
int N = sz(s)-2, K = sz(C);
lBeli[0] = 0;
for(int i = 1; i <= N; i++) lBeli[i] = (s[i] == '_' ? i:lBeli[i-1]);
rBeli[N+1] = N+1;
for(int i = N; i >= 1; i--) rBeli[i] = (s[i] == '_' ? i:rBeli[i+1]);
///dpL
dpL[0][0] = true;
for(int i = 1; i <= N; i++) {
dpL[0][i] = (dpL[0][i-1] && s[i] != 'X');
dpLK[0][i] = true;
}
for(int j = 1; j <= K; j++) {
dpLK[j][0] = false;
for(int i = 1; i <= N; i++) {
if(!(lBeli[i] <= i-C[j-1] && s[i-C[j-1]] != 'X')) dpLK[j][i] = false;
else if(i-C[j-1] == 0) dpLK[j][i] = (j == 1 ? true:false);
else dpLK[j][i] = dpL[j-1][i-C[j-1]-1];
dpL[j][i] = (dpL[j][i-1]||dpLK[j][i]);
}
}
///dpR
dpR[0][N+1] = true;
for(int i = N; i >= 1; i--) {
dpR[0][i] = (dpR[0][i+1] && s[i] != 'X');
dpRK[0][i] = true;
}
for(int j = 1; j <= K; j++) {
dpRK[j][N+1] = false;
dpR[j][N+1] = false;
for(int i = N; i >= 1; i--) {
if(!(rBeli[i] >= i+C[K-j] && s[i+C[K-j]] != 'X')) dpRK[j][i] = false;
else if(i+C[K-j] == N+1) dpRK[j][i] = (j == 1 ? true:false);
else dpRK[j][i] = dpR[j-1][i+C[K-j]+1];
dpR[j][i] = (dpR[j][i+1]||dpRK[j][i]);
}
}
///da li moze beo
for(int i = 1; i <= N; i++) {
if(s[i] == 'X') continue;
if(s[i] == '_') {
b[i] = true;
continue;
}
for(int j = 0; j <= K; j++) {
if(dpL[j][i-1] && dpR[K-j][i+1]) {
b[i] = true;
break;
}
}
}
///da li moze crn
for(int j = 1; j <= K; j++) {
int duz = C[j-1], posl = -1;
for(int i = N; i >= 1; i--) {
if(dpLK[j][i] && s[i+1] != 'X') {
if(i == N && j == K) posl = i;
else if(i != N && dpR[K-j][i+2]) posl = i;
}
if(posl <= i+duz-1) c[i] = true;
}
}
string res = "";
for(int i = 1; i <= N; i++) {
if(b[i] && c[i]) res += '?';
else if(b[i]) res += '_';
else if(c[i]) res += 'X';
}
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |