Submission #204497

#	Time	Username	Problem	Language	Result	Execution time	Memory
204497		anonymous	Paint By Numbers (IOI16_paint)	C++14	90 / 100	23 ms	18680 KiB

paint

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