#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
bool dp1[200001][101],vis[200001][101];
int siz[101],pre[200001][2],w[2000001],b[200001];
int n,k;
string s;
int sum(int l,int r,int u){
return pre[r][u]-pre[l-1][u];
}
bool dfs1(int i,int gr){
if(vis[i][gr]!=0) return dp1[i][gr];
if(i==n+1){
if(gr==k+1) return 1;
return 0;
}
vis[i][gr]=1;
if(s[i]=='X') return 0;
if(i<=n){
if(dfs1(i+1,gr)==1){
dp1[i][gr]=1;
w[i]++;
w[i+1]--;
}
}
if(i+siz[gr]<=n&&gr!=k+1&&sum(i+1,i+siz[gr],0)==0){
if(dfs1(i+siz[gr]+1,gr+1)==1){
dp1[i][gr]=1;
w[i]++;
w[i+1]--;
b[i+1]++;
b[i+siz[gr]+1]--;
}
}
return dp1[i][gr];
}
string solve_puzzle(string t, vector<int> c) {
s='#'+t;
n=s.size()-1;k=c.size();
for(int i=0;i<c.size();i++) siz[i+1]=c[i];
for(int i=1;i<=n;i++){
if(s[i]=='X') pre[i][1]++;
if(s[i]=='_') pre[i][0]++;
pre[i][0]+=pre[i-1][0];
pre[i][1]+=pre[i-1][1];
}
if(sum(1,siz[1],0)==0&&dfs1(siz[1]+1,2)==1){
b[1]++;
b[siz[1]+1]--;
}
dfs1(1,1);
int sum1=0,sum2=0;
string ans="";
for(int i=1;i<=n;i++){
sum1+=w[i];
sum2+=b[i];
if(sum1>0&&sum2>0) ans+='?';
else if(sum1>0) ans+='_';
else ans+='X';
}
return ans;
}
Compilation message (stderr)
paint.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
paint_c.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
# | 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... |