이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 2e5+5;
const int mxk = 105;
int n, k;
int pref_b[mxn], pref_w[mxn];
bool dp[mxk][mxn], dp_pref[mxk][mxn];
bool must_b[mxn], can_b[mxn];
bool check(int pref[], int l, int r) {
return pref[r] == pref[l-1];
}
// TODO: handle case where there are Xs on the right side and invalidate some ending positions
string solve_puzzle(string s, vector<int> C) {
n = s.size(), k = C.size();
s = "$"+s;
C.insert(C.begin(), -1);
for(int i = 1; i <= n; i++) {
pref_b[i] = pref_b[i-1]+(s[i]=='X');
pref_w[i] = pref_w[i-1]+(s[i]=='_');
}
dp[0][0] = true;
for(int i = C[0]; i <= n; i++) {
if(s[i] != 'X') {
dp_pref[0][i] = dp_pref[0][i-1];
}
dp_pref[0][i] |= dp[0][i];
}
for(int f = 1; f <= k; f++) {
for(int i = C[f]; i <= n; i++) {
if(((i > C[f] && dp_pref[f-1][i-C[f]-1]) || (i == C[f] && f == 1))
&& check(pref_w, i-C[f]+1, i) && check(pref_b, i-C[f], i-C[f])) {
dp[f][i] = true;
}
}
for(int i = C[f]; i <= n; i++) {
if(s[i] != 'X') {
dp_pref[f][i] = dp_pref[f][i-1];
}
dp_pref[f][i] |= dp[f][i];
}
}
// mark certain X
for(int f = k, rmost_start = n; f > 0; f--) {
int l = 0, r = n;
int rmost = 0;
for(int i = 0; i <= rmost_start; i++) {
if(dp[f][i]) {
r = min(r, i);
l = max(l, i-C[f]+1);
rmost = max(rmost, i);
}
}
for(int i = l; i <= r; i++) {
must_b[i] = true;
}
rmost_start = rmost-C[f]-1;
}
// mark possible X
for(int f = k, rmost_start = n; f > 0; f--) {
int cnt = 0;
int rmost = 0;
for(int i = rmost_start; i >= 0; i--) {
if(dp[f][i]) {
cnt = C[f];
rmost = max(rmost, i);
}
if(cnt > 0) can_b[i] = true;
cnt--;
}
rmost_start = rmost-C[f]-1;
}
string ans(n, '?');
for(int i = 1; i <= n; i++) {
if(!can_b[i]) {
ans[i-1] = '_';
}
else if(must_b[i]) {
ans[i-1] = 'X';
}
if(s[i] == '_') {
ans[i-1] = '_';
}
if(s[i] == 'X') {
ans[i-1] = 'X';
}
}
return ans;
}
/*
..........
2
3 4
........
2
3 4
..._._....
1
3
.X........
1
3
*/
# | 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... |