# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
291414 | REALITYNB | Paint By Numbers (IOI16_paint) | C++14 | 0 ms | 0 KiB |
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 <bits/stdc++.h>
#define B 1
#define W 0
using namespace std;
int n , k ;
vector<int> b , w , p , c ;
string a ;
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 ;
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 ;
ok |=okk ;
}
if(i+c[j]<=n&¬hing(i,i+c[j]-1)){
bool okk = dp(i+c[j],j+1,W) ;
if(okk) b[i]++ , b[i+c[j]]-- ;
ok |=okk ;
//if(ok) ok&=isthere(i,)
}
}
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++){
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("..........",{}) ;
cout << ans ;
}