Submission #343711

#	Time	Username	Problem	Language	Result	Execution time	Memory
343711		bigDuck	Paint By Numbers (IOI16_paint)	C++14	7 / 100	1 ms	364 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



bool suf1[200010][100], pref1[200010][100];//negre

bool suf2[200010][100], pref2[200010][100];//albe

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


int N, K;
string S;
vector<int> C;

int sum2[200010][101];
int sum3[200010][101];
void build(){

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


pref1[0][0]=false;
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]) ){
            if( (get_sum(i-C[j-1]+1, i)==0) && ( (pref2[i-C[j-1] ][j-1]==true) ) ){
                pref1[i][j]=true;
            }
        }
        if( (S[i-1]!='X') && (  (pref1[i-1][j]==true) || (pref2[i-1][j]==true)  )   ){
            pref2[i][j]=true;
        }
    }
}

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



}




string res;

int get_sum2(int l, int r, int j){
    return sum2[r][j]-sum2[l-1][j];
}

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

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

    for(int i=1; i<=N; i++){
        bool white=false, black=false;
        for(int j=0; j<=K; j++){
            if( (j>0) && (  (pref1[i][j] && (suf2[i+1][K-j]) ) || (suf1[i][j] && (pref2[i-1][K-j])) ||  ((((i+C[j-1]-1)<=N) && (get_sum2(i, i+C[K-j]-1, j)) ) || (((i-C[K-j]+1)>=1) && (get_sum3(i-C[K-j]+1, i, j)) ) ))  ){
                black=true;
            }
            if(  (  (pref1[i-1][j] || pref2[i-1][j] ) && suf2[i][K-j] ) || (  pref2[i][j] && (suf1[i+1][K-j] || suf2[i+1][K-j]) )  ){
                white=true;
            }
        }
        //cout<<i<<" "<<white<<" "<<black<<"\n";
        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();
    S=s; C=c;
    build();
    build_res();
    return res;
}

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