Submission #263524

#	Time	Username	Problem	Language	Result	Execution time	Memory
263524		Black_Ghost	Paint By Numbers (IOI16_paint)	C++17	100 / 100	773 ms	93392 KiB

paint

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ss second
#define ff first
#define pb push_back
#define mp make_pair
int n;
string x;
int dp[200010][102];
int p[200100];
int pls[200100],pls2[200100];
int sm[200100];
int k2;
int go(int cr,int cr2){
    if(cr>n){
        if(cr2!=k2)return 0;
        else {return 1;}
    }
    int &ret=dp[cr][cr2];
    if(ret!=-1)return ret;
    ret=0;
    if(x[cr]=='_'){
        ret=max(ret,go(cr+1,cr2));
    }
    if(x[cr]=='.'){
        ret=max(ret,go(cr+1,cr2));
        if(ret==1){
            pls2[cr]++;
            pls2[cr+1]--;
        }
        if(cr2<k2&&cr+p[cr2]-1<=n){
                //cout<<x[cr+p[cr2]]<<' '<<sm[cr+p[cr2]-1]-sm[cr-1]<<endl;
            if(x[cr+p[cr2]]!='X'&&sm[cr+p[cr2]-1]-sm[cr-1]==0){

                ret=max(ret,go(cr+p[cr2]+1,cr2+1));
                if(go(cr+p[cr2]+1,cr2+1)){
                    pls[cr]++;//cout<<cr<<endl;
                    pls[cr+p[cr2]]--;
                    if(x[cr+p[cr2]]=='.'){
                        pls2[cr+p[cr2]]++;
                        pls2[cr+p[cr2]+1]--;
                        //cout<<cr+p[cr2]<<endl;
                    }

                }
            }
        }
    }
    if(x[cr]=='X'){
         if(cr2<k2&&cr+p[cr2]-1<=n){
                //cout<<x[cr+p[cr2]]<<' '<<sm[cr+p[cr2]-1]-sm[cr-1]<<endl;
            if(x[cr+p[cr2]]!='X'&&sm[cr+p[cr2]-1]-sm[cr-1]==0){

                ret=max(ret,go(cr+p[cr2]+1,cr2+1));
                if(go(cr+p[cr2]+1,cr2+1)){
                    pls[cr]++;//cout<<cr<<endl;
                    pls[cr+p[cr2]]--;
                    if(x[cr+p[cr2]]=='.'){
                        pls2[cr+p[cr2]]++;
                        pls2[cr+p[cr2]+1]--;
                        //cout<<cr+p[cr2]<<endl;
                    }

                }
            }
        }

    }
    return ret;
}
string solve_puzzle(string s, vector<int> c){
     n=s.size();
     int k=c.size();
     k2=k;

     x='0'+s+"___";

     memset(dp,-1,sizeof dp);
     for(int i=0;i<k;i++)p[i]=c[i];
     for(int i=1;i<=n;i++){
        sm[i]=sm[i-1]+(x[i]=='_');
     }
     go(1,0);
     string ans="";
     int sum1=0,sum2=0;
     for(int i=1;i<=n;i++){
        sum1+=pls[i];
        sum2+=pls2[i];
        if(x[i]=='X')ans+='X';
        else if(x[i]=='_')ans+='_';
        else {
            if(sum1>0&&sum2>0)ans+='?';
            else if(sum1)ans+='X';
            else if(sum2)ans+='_';
        }
        //cout<<sum1<<' '<<sum2<<endl;
     }
     return 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