Submission #291445

#	Time	Username	Problem	Language	Result	Execution time	Memory
291445		REALITYNB	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1395 ms	174916 KiB

paint

#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[200001][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 ; 
}*/

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10