Submission #727619

#TimeUsernameProblemLanguageResultExecution timeMemory
727619Yell0Paint By Numbers (IOI16_paint)C++17
7 / 100
1 ms212 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; string solve_puzzle(string s,vector<int> c) { int N=s.size(),K=c.size(); s.insert(s.begin(),'.'); c.insert(c.begin(),0); // pf/sf vector<int> pfb(N+2,0),pfw(N+2,0); for(int i=1;i<=N;++i) { pfb[i]=pfb[i-1]+(s[i]=='X'); pfw[i]=pfw[i-1]+(s[i]=='_'); } // dp vector<vector<int>> pfdp(N+3,vector<int>(K+3)),sfdp(N+3,vector<int>(K+3)); for(int i=0;i<=N;++i) { for(int j=0;j<=K;++j) { if(!j) { pfdp[i][j]=!pfb[i]; continue; } if(c[j]>i) { pfdp[i][j]=0; continue; } bool fb,fw; if(s[i-c[j]]=='X'||(pfw[i]-pfw[i-c[j]])) fb=0; else fb=pfdp[max(0,i-c[j]-(j>1))][j-1]; fw=pfdp[i-1][j]; if(s[i]=='X') pfdp[i][j]=fb; else if(s[i]=='_') pfdp[i][j]=fw; else pfdp[i][j]=fb||fw; } } for(int i=N+1;i>0;--i) { for(int j=K+1;j>0;--j) { if(j==K+1) { sfdp[i][j]=!(pfb[N]-pfb[i-1]); continue; } if(c[j]>N-i+1) { sfdp[i][j]=0; continue; } bool fb,fw; if(s[i+c[j]]=='X'||(pfw[i+c[j]-1]-pfw[i-1])) fb=0; else fb=sfdp[min(N,i+c[j]+(j<K))][j+1]; fw=sfdp[i+1][j]; if(s[i]=='X') sfdp[i][j]=fb; else if(s[i]=='_') sfdp[i][j]=fw; else sfdp[i][j]=fb||fw; } } vector<bool> b(N+2),w(N+2); // can be white? for(int i=1;i<=N;++i) { if(s[i]=='_') w[i]=1; else if(s[i]=='X') w[i]=0; else for(int j=0;j<=K;++j) if(pfdp[i-1][j]&&sfdp[i+1][j+1]) w[i]=1; } // can be black vector<int> diff(N+2); for(int i=1;i<=K;++i) { for(int j=1;j+c[i]-1<=N;++j) { bool v=1; if(s[j-1]=='X'||s[j+c[i]]=='X') v=0; if(pfw[j+c[i]-1]-pfw[j-1]) v=0; if(!pfdp[max(0,j-2)][i-1]||!sfdp[min(N,j+c[i]+1)][i+1]) v=0; if(v) { ++diff[j]; --diff[j+c[i]]; } } } int sum=0; for(int i=1;i<=N;++i) { sum+=diff[i]; b[i]=sum>0; } string ans=""; for(int i=1;i<=N;++i) { if(w[i]&&b[i]) ans.push_back('?'); else if(w[i]) ans.push_back('_'); else if(b[i]) ans.push_back('X'); } return ans; }
#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...