Submission #343757

#	Time	Username	Problem	Language	Result	Execution time	Memory
343757		bigDuck	Paint By Numbers (IOI16_paint)	C++14	100 / 100	744 ms	239740 KiB

paint

#include "paint.h"

#include <cstdlib>

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount


string res;

int N, K;
vector<int> C;
string S;
bool suf1[200010][101], pref1[200010][101];
bool suf2[200010][101], pref2[200010][101];

int sum[200010];
int sum2[200010][101], sum3[200010][101];




int get_sum(int l, int r){
    return sum[r]-sum[l-1];
}

int get_sum2(int l, int j){
    return sum2[min(l+C[j-1]-1, N) ][j]-sum2[l-1][j];
}

int get_sum3(int r, int j){
    return sum3[r][j]-sum3[max(r-C[K-j]+1-1, 1) ][j];
}


void build(){


    for(int i=1; i<=N; i++){
        sum[i]=sum[i-1];
        if(S[i-1]=='_'){
            sum[i]++;
        }
    }


    pref2[0][0]=true;
    for(int i=1; i<=N; i++){
        for(int j=0; j<=K; j++){
            if( (j>0) && (i>=(C[j-1])) && ( get_sum(i-C[j-1]+1, i)==0    )  && ( pref2[i-C[j-1] ][j-1]   ) ){
                pref1[i][j]=true;
            }
            if( (S[i-1]!='X') && ( (pref2[i-1][j]==true) || (pref1[i-1][j]==true) ) ){
                pref2[i][j]=true;
            }
        }
    }

    suf2[N+1][0]=true;
    for(int i=N; i>=1; i--){
        for(int j=0; j<=K; j++){
            if((j>0) && ( (i+C[K-j]-1)<=N )  && (get_sum(i, i+C[K-j]-1)==0 ) && (suf2[i+C[K-j] ][j-1]==true) ){
                suf1[i][j]=true;
            }
            if(  (S[i-1]!='X') && ( (suf1[i+1][j]==true) || (suf2[i+1][j]==true) ) ){
                suf2[i][j]=true;
            }
        }
    }


    for(int i=1; i<=N; i++){
        for(int j=0; j<=K;j++){
            sum2[i][j]=sum2[i-1][j];
            if( (pref1[i][j]==true) &&(suf2[i+1][K-j]==true) ){
                sum2[i][j]++;
            }
            sum3[i][j]=sum3[i-1][j];
            if(  (suf1[i][j]==true)  && (pref2[i-1][K-j]==true) ){
                sum3[i][j]++;
            }
        }
    }

}



void build_res(){

    res.resize(N);
    for(int i=0; i<N; i++){
        res[i]='?';
    }

    for(int i=1; i<=N; i++){
        bool black=false; bool white=false;
        for(int j=0; j<=K; j++){
            if(  ( (j>0) && ( (  get_sum2(i, j)>0  )   )  ) || ( (j>0) && (get_sum3(i, j)) )  ){
                black=true;
            }
            if(   ( (pref2[i][j]==true) && ( (suf1[i+1][K-j]==true) || (suf2[i+1][K-j]==true) ) )  ){
                white=true;
            }
        }
        if( (white) && (black) ){
            res[i-1]='?';
        }
        else{
            if(white){
                res[i-1]='_';
            }
            else{
                res[i-1]='X';
            }
        }
    }
}



std::string solve_puzzle(std::string s, std::vector<int> c) {
    N=s.length(); K=c.size();
    C=c; S=s;
    build();
    build_res();
    return res;
}

• 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