이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long; using vi = vector<int>;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr,__VA_ARGS__)
#define ensure(...) if (!(__VA_ARGS__)){ fprintf(stderr,"Error in %dth line.", __LINE__), exit(-1); }
const int N = 103, K = 103;
int n, k;
bool valid(const string &s, const vi &c) {
bool dp[N][K]{};
int _pfx[N]{};
rep(i,1,n) _pfx[i]=_pfx[i-1]+(s[i]=='_');
rep(i,1,n) {
if (s[i] == 'X') {
rep(j,i,i+c[1]-1) {
if (s[j] == '_') break;
if (c[1] <= j and _pfx[j]-_pfx[j-c[1]] == 0)
dp[j][1] = true;
}
break;
}
if (i >= c[1] and _pfx[i]-_pfx[i-c[1]] == 0) {
dp[i][1] = true;
}
}
rep(i,1,n) if (s[i] != '_') {
rep(j,2,k) {
bool flag = 1;
per(x,i-c[j]+1,i) if (s[x] == '_') flag = 0;
if (s[i-c[j]] == 'X') flag = 0;
if (!flag) continue;
per(x,1,i-c[j]-1) {
if (s[x] == '_') break;
dp[i][j] |= dp[x][j-1];
}
}
}
// rep(i,1,n) rep(j,1,k) cerr << dp[i][j] << " \n"[j == k];
per(i,1,n) {
if (i < n and s[i+1] == 'X') break;
if (dp[i][k]) return true;
}
return false;
}
string solve_puzzle(string s, vi c) {
n = siz(s), k = siz(c);
s = "$"+s, c.insert(begin(c),0);
string res(n,'$');
// valid("$X.._._....",c);
rep(i,1,n) {
char x = s[i];
if (x != '.') {
res[i-1] = x;
continue;
}
s[i] = 'X'; if (not valid(s,c)) res[i-1] = '_';
s[i] = '_'; if (not valid(s,c)) res[i-1] = 'X';
if (res[i-1] == '$') res[i-1] = '?';
s[i] = x;
}
return res;
}
#ifdef LOCAL
const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];
int main() {
ensure(1 == scanf("%s", buf));
std::string s = buf;
int c_len;
ensure(1 == scanf("%d", &c_len));
std::vector<int> c(c_len);
for (int i = 0; i < c_len; i++) {
ensure(1 == scanf("%d", &c[i]));
}
std::string ans = solve_puzzle(s, c);
printf("%s\n", ans.data());
return 0;
}
#endif
# | 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... |