Submission #291443

#TimeUsernameProblemLanguageResultExecution timeMemory
291443REALITYNBPaint By Numbers (IOI16_paint)C++14
90 / 100
304 ms327544 KiB
#include <bits/stdc++.h> #define B 1 #define W 0 using namespace std; int n , k ; vector<int> b , w , p , c ; string a ; int mem[200000][101][2] ; bool nothing(int i , int j){ int minus = 0 ; if(i) minus=p[i-1] ; return (minus==p[j]) ; } bool dp(int i , int j , int lastcolor){ if(i==n&&j==k) return 1 ; if(i>=n) return 0 ; if(mem[i][j][lastcolor]!=-1) return mem[i][j][lastcolor] ; bool ok =0; if(lastcolor==B||j==k){ if(a[i]!='X') ok = dp(i+1,j,W) ; if(ok) w[i] =1 ; } else{ if(a[i]!='X'){ bool okk = dp(i+1,j,W) ; if(okk) w[i] = 1 ; // if(i==1) cout << okk << " " ; ok |=okk ; } if(i+c[j]<=n&&nothing(i,i+c[j]-1)){ bool okk = dp(i+c[j],j+1,B) ; if(okk) b[i]++ , b[i+c[j]]-- ; // ok =okk ; ok |=okk ; //if(ok) ok&=isthere(i,) } } mem[i][j][lastcolor] =ok; return ok ; } string solve_puzzle(string aa , vector<int> cc){ a = aa ; c= cc ; n = a.size() ; k=c.size() ; b.resize(n+1); w.resize(n+1) ; p.resize(n+1) ; for(int i=0;i<=n;i++) for(int j=0;j<=k;j++) mem[i][j][1]=mem[i][j][0]=-1 ; for(int i=0;i<n;i++){ if(a[i]=='_') p[i]++ ; if(i) p[i]+=p[i-1] ; } dp(0,0,W) ; string ans ; for(int i=0;i<n;i++){ if(i)b[i]+=b[i-1] ; if(b[i]&&w[i])ans+='?' ; else if(b[i]) ans+='X' ; else ans+='_' ; } return ans ; } /*int main(){ string ans = solve_puzzle("..........", {3, 4}) ; cout << 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...