Submission #598185

#TimeUsernameProblemLanguageResultExecution timeMemory
598185chirathnirodhaPaint By Numbers (IOI16_paint)C++17
7 / 100
12 ms19880 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...