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 "paint.h"
#include<bits/stdc++.h>
#include <cstdlib>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first
#define S second
bool dp[200000][100];
int lastblack[200000];
void createdp(string s,int n,int k,vector<int> c){
memset(dp,false,sizeof(dp));
int lb[n],lw[n];
int cb=-1,cw=-1;
for(int i=0;i<n;i++){
lb[i]=cb;lw[i]=cw;
if(s[i]=='X')cb=i;
if(s[i]=='_')cw=i;
}
vector<int> lastval[k];
for(int i=0;i<n;i++){
for(int j=0;j<k;j++){
if(s[i]=='_' || i-c[j]<-1)continue;
if(i-c[j]==-1){
if(lw[i]<=i-c[j] && j==0){
dp[i][j]=true;
lastval[j].PB(i);
}
continue;
}
if(lw[i]>i-c[j])continue;
int lastbl=lb[i-c[j]+1];
if(j==0 && lastbl!=-1)continue;
if(j>0){
auto low=lower_bound(lastval[j-1].begin(),lastval[j-1].end(),lastbl);
if(low==lastval[j-1].end() || *low>=i-c[j])continue;
}
dp[i][j]=true;
lastval[j].PB(i);
}
}
}
string solve_puzzle(string s, vector<int> c) {
int n=s.size(),k=c.size();
bool pref[n][k],suf[n][k];
vector<int> left[k],right[k];
string revs=s;reverse(revs.begin(),revs.end());
vector<int> revc=c;reverse(revc.begin(),revc.end());
createdp(s,n,k,c);
for(int i=0;i<n;i++)for(int j=0;j<k;j++)pref[i][j]=dp[i][j];
createdp(revs,n,k,revc);
for(int i=0;i<n;i++)for(int j=0;j<k;j++)suf[n-1-i][k-1-j]=dp[i][j];
for(int i=0;i<n;i++){
for(int j=0;j<k;j++){
if(pref[i][j])left[j].PB(i);
if(suf[i][j])right[j].PB(i);
}
}
int nearbl[n][2];
nearbl[0][0]=-1;nearbl[n-1][1]=n;
int nel[n][k],ner[n][k];
for(int j=0;j<k;j++)nel[0][j]=-1,ner[n-1][j]=n;
for(int i=0;i<n-1;i++){
if(s[i]=='X')nearbl[i+1][0]=i;
else nearbl[i+1][0]=nearbl[i][0];
for(int j=0;j<k;j++){
if(pref[i][j])nel[i+1][j]=i;
else nel[i+1][j]=nel[i][j];
}
}
for(int i=n-1;i>0;i--){
if(s[i]=='X')nearbl[i-1][1]=i;
else nearbl[i-1][1]=nearbl[i][1];
for(int j=0;j<k;j++){
if(suf[i][j])ner[i-1][j]=i;
else ner[i-1][j]=ner[i][j];
}
}
string res=s;
for(int i=0;i<n;i++){
if(res[i]=='_' || res[i]=='X')continue;
for(int j=-1;j<k;j++){
if(j==-1 && nearbl[i][0]!=-1)continue;
if(j!=-1 && (nel[i][j]==-1 || nearbl[i][0]>nel[i][j]))continue;
if(j==k-1 && nearbl[i][1]!=n)continue;
if(j!=k-1 && (ner[i][j+1]==n || nearbl[i][1]<ner[i][j+1]))continue;
res[i]='W';
break;
}
}
bool proc[n];memset(proc,false,sizeof(proc));
for(int j=0;j<k;j++){
if(j==k-1){
for(int i=0;i<n;i++){
if(nearbl[i][1]!=n || pref[i][j]==false)continue;
for(int l=0;l<c[j];l++){
if(proc[i-l])break;
proc[i-l]=true;
if(res[i-l]=='.')res[i-l]='X';
if(res[i-l]=='W')res[i-l]='?';
}
}
break;
}
int cur=0;
while(cur<n){
if(pref[cur][j]){
if(ner[cur][j+1]==n || ner[cur][j+1]>nearbl[cur][1]);
else {
for(int i=0;i<c[j];i++){
if(proc[cur-i])break;
proc[cur-i]=true;
if(res[cur-i]=='.')res[cur-i]='X';
if(res[cur-i]=='W')res[cur-i]='?';
}
}
}
cur++;
}
}
for(int i=0;i<n;i++)if(res[i]=='W')res[i]='_';
return res;
}
# | 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... |