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>
using namespace std;
bool space[200001];
int add[200002];
bool dp[200001][101], dp2[200001][101];
int sum[200001];
string solve_puzzle(string s, vector<int> c){
int n = s.length(), k = c.size();
dp[0][0] = 0;
for(int i=1;i<=n;i++){
if(s[i-1] == '.' || s[i-1] == 'X') sum[i]++;
sum[i] += sum[i-1];
}
dp[0][0] = 1;
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
if(dp[i-1][j] && (s[i-1] == '_' || s[i-1] == '.')) dp[i][j] = 1;
if(j == 0){
if(j < k && i >= c[j] && sum[i]-sum[i-c[j]] == c[j] && dp[i-c[j]][j]){
dp[i][j+1] = 1;
}
}
else{
if(j < k && i >= c[j]+1 && sum[i]-sum[i-c[j]] == c[j] && (s[i-c[j]] == '_' || s[i-c[j]] == '.')){
dp[i][j+1] |= dp[i-c[j]-1][j];
}
}
}
}
dp2[n][k] = 1;
for(int i=n;i>=1;i--){
for(int j=k;j>=0;j--){
if(dp2[i][j]){
if(dp[i-1][j] && (s[i-1] == '_' || s[i-1] == '.')){
dp2[i-1][j] = 1;
space[i] = 1;
}
if(j == 1){
if(j > 0 && i >= c[j-1] && sum[i]-sum[i-c[j-1]] == c[j-1] && dp[i-c[j-1]][j-1]){
add[i]++;
add[i-c[j-1]]--;
dp2[i-c[j-1]][j-1] = 1;
}
}
else{
if(j > 0 && i >= c[j-1]+1 && sum[i]-sum[i-c[j-1]] == c[j-1] && (s[i-c[j-1]] == '_' || s[i-c[j-1]] == '.')){
add[i]++;
add[i-c[j-1]]--;
space[i-c[j-1]] = 1;
dp2[i-c[j-1]-1][j-1] = 1;
}
}
}
}
}
string ans = "";
for(int i=0;i<n;i++) ans += '?';
for(int i=n;i>=1;i--){
add[i] += add[i+1];
if(add[i] && !space[i]) ans[i-1] = 'X';
else if(!add[i] && space[i]) ans[i-1] = '_';
}
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... |