Submission #204502

#	Time	Username	Problem	Language	Result	Execution time	Memory
204502		anonymous	Paint By Numbers (IOI16_paint)	C++14	100 / 100	576 ms	54136 KiB

paint

#include "paint.h"
#include <iostream>
#include<string>
#include<vector>
#define MAXN 200005
#define MAXK 105
using namespace std;
int N, K, whitesum[MAXN], canblack[MAXN], black;
bool dp[MAXN][MAXK], done[MAXN][MAXK], canwhite[MAXN];
string s;
vector <int> c;
bool gen(int i, int j) {
    if (i >= N && j == K) {return(1);}
    if (i >= N && j < K) {return(0);}
    if (done[i][j]) {return(dp[i][j]);}
    done[i][j]=true;
    if (s[i] != 'X' && gen(i+1,j)) {
        dp[i][j]=true;
        canwhite[i]=true;
    }
    if (j < K && i + c[j] <= N) {
        bool can = true;
        if (whitesum[i+c[j]] - whitesum[i] > 0 || (i+c[j] != N && s[i+c[j]] == 'X')) {
            can=false;
        }
        if (can && gen(i+c[j]+1, j+1)) {
            dp[i][j]=true;
            canblack[i]++;
            canblack[i+c[j]]--;
            canwhite[i+c[j]]=true;
        }
    }
    return(dp[i][j]);
}
string solve_puzzle(string S, vector<int> C) {
    N=S.size(), K=C.size();
    s = S, c = C;
    for (int i=1; i<=N; i++) {
        whitesum[i]=whitesum[i-1] + (S[i-1] == '_');
    }
    gen(0,0);
    string Sol;
    for (int i=0; i<N; i++) {
        black+=canblack[i];
        if (black && canwhite[i]) {
            Sol.push_back('?');
        } else if (black) {
            Sol.push_back('X');
        } else {
            Sol.push_back('_');
        }
    }
    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: 10 / 10