Submission #21798

#	Time	Username	Problem	Language	Result	Execution time	Memory
21798		sampriti	Paint By Numbers (IOI16_paint)	C++14	90 / 100	293 ms	265008 KiB

paint

#include "paint.h"
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cassert>
#include <cstdio>
 
#define NMAX 200010
#define KMAX 110
 
using namespace std;
 
int pr[NMAX];
int nx[NMAX];
 
int dp1[NMAX][KMAX];
int dp2[NMAX][KMAX];
 
string S;
int N,K;
 
int A[NMAX];
 
int fst,lst;
 
int wht[NMAX];
int blk[NMAX];
 
void init(){
    int i,p;
 
    p = -1;
    for(i = 0; i < N; ++i){
        pr[i] = p;
        if(S[i] == '_') p=i;
    }
 
    p = N;
    for(i = N-1; i >=0 ; --i){
        nx[i] = p;
        if(S[i] == '_') p =i;
    }
 
    for(i = 0; i < N;++i) if(S[i] == 'X') break;
    fst =(i < N ? i : 100);
 
    for(i = N-1; i >= 0; --i) if(S[i] == 'X') break;
    lst =(i >= 0 ? i : -100);
}
 
inline int getdp1(int i, int k){
    if(i < 0 && k >= 0) return 0;
    if(i < 0) return 1;
    if(k < 0) return fst > i;
    return dp1[i][k];
}
 
inline int getdp2(int i, int k){
    if(i >= N && k < K) return 0;
    if(i >= N) return 1;
    if(k >= K) return lst < i;
    return dp2[i][k];
}
 
int st[NMAX][KMAX];
 
void dodp(){
    int i,k;
 
    for(i = 0; i < N; ++i){
        for(k =0 ; k < K; ++k){
            dp1[i][k]=0;
            if(S[i] != 'X') dp1[i][k] |= getdp1(i-1,k);
 
            if(S[i] == '_' || i-A[k]+1 < 0  || pr[i] > i-A[k]) continue;
            if(i-A[k] >= 0 && S[i-A[k]] == 'X') continue;
 
            dp1[i][k] |= getdp1(i-A[k]-1,k-1);
        }
    }
 
    for(i = N-1; i >= 0; --i){
        for(k = K-1;k >= 0; --k){
            dp2[i][k]=0;
 
            if(S[i] != 'X') dp2[i][k] |= getdp2(i+1,k);
 
            if(S[i] == '_' || i+A[k] > N || nx[i] < i+A[k]) continue;
            if(i+A[k] < N && S[i+A[k]]=='X') continue;
            if(!getdp2(i+A[k]+1,k+1)) continue;
 
            dp2[i][k]=1;
            st[i][k]=1;
        }
    }
 
}
 
int mx;
 
inline int check_white(int i){
    if(S[i] == 'X') return 0;
    int k;
    for(k =0 ; k <= K; ++k) if(getdp1(i-1,k-1) && getdp2(i+1,k)) return 1;
    return 0;
}
 
inline int check_black(int i){
    if(S[i] == '_') return 0;
 
    int b = (i <= mx);
    int k;
 
    if(S[i-1] == 'X') return b;
 
    for(k =0; k < K; ++k){
        if(!getdp1(i-2,k-1) || !st[i][k]) continue;
        b = 1;
        mx = max(mx,i+A[k]-1);
    }
 
    return b;
}
 
string sol;
 
std::string solve_puzzle(std::string s, std::vector<int> c) {
    N= s.size();
    K=c.size();
 
    int i;
    S = s;
    for(i =0 ; i < K; ++i) A[i]=c[i];
    mx=-1;
    init();
    dodp();
 
    for(i = 0; i < N; ++i){
        wht[i] = check_white(i);
        blk[i] = check_black(i);
    }
 
 
    for(i = 0; i < N; ++i){
        if(wht[i] && blk[i]){
            sol.push_back('?');
            continue;
        }
        sol.push_back(blk[i] ? 'X' : '_');
    }
 
    return sol;
}

• 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: 0 / 10