이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "paint.h"
#include <cstring>
#include <string>
#include <cstdlib>
#include <cassert>
#include <string>
#include <vector>
using namespace std;
string S;
vector<int> A;
int N, K;
int dp[200000][101][2]; // dp[i][j][k] = is it possible to have valid string for i...N with clues j...K and current character (k=0|black or 1|white)
int pref[2][200000];
int get_sum(int i, int L, int R) {
if(L == 0) return pref[i][R];
return pref[i][R] - pref[i][L - 1];
}
int solve(int i, int j, int k) {
if(i == N) return (j == K);
if(dp[i][j][k] != -1) return dp[i][j][k];
int ans = 0;
if(k == 0) {
if(S[i] != '_' && j < K) {
if(get_sum(1, i, i + A[j] - 1) == 0 && i + A[j] <= N) {
ans = solve(i + A[j], j + 1, 1);
}
}
}
else {
if(S[i] != 'X') ans = solve(i + 1, j, 0) | solve(i + 1, j, 1);
}
return dp[i][j][k] = ans;
}
string solve_puzzle(string _S, vector<int> _A) {
S = _S;
A = _A;
N = S.length();
K = A.size();
memset(pref, 0, sizeof pref);
if(S[0] == 'X') pref[0][0]++;
else if(S[0] == '_') pref[0][1]++;
for(int i = 1; i < N; i++) {
pref[0][i] = pref[0][i - 1];
pref[1][i] = pref[1][i - 1];
if(S[i] == 'X') pref[0][i]++;
else if(S[i] == '_') pref[1][i]++;
}
memset(dp, -1, sizeof dp);
solve(0, 0, 0);
solve(0, 0, 1);
string ans = "";
int ptr = -1;
for(int i = 0; i < N; i++) {
bool white_pos = false;
for(int j = 0; j <= K; j++) {
if(dp[i][j][0] == 1) ptr = max(ptr, i + A[j] - 1);
if(dp[i][j][1] == 1) white_pos = true;
}
bool black_pos = (i <= ptr);
if(black_pos && white_pos) ans += '?';
else if(black_pos) ans += 'X';
else if(white_pos) ans += '_';
else assert(false);
}
return ans;
}
# | 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... |