Submission #200989

#	Time	Username	Problem	Language	Result	Execution time	Memory
200989		AQT	Paint By Numbers (IOI16_paint)	C++14	0 / 100	5 ms	376 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"

using namespace std;

long long pre[2][200005];
bool dp[2][105][200005];
int par[2][105][200005];

string solve_puzzle(string s, vector<int> c){
    int N = s.size(), K = c.size();
    for(int i = 1; i<=N; i++){
        if(s[i-1] == '_'){
            pre[0][i] = 1;
        }
        else if(s[i-1] == 'X'){
            pre[1][i] = 1;
        }
        pre[0][i] += pre[0][i-1];
        pre[1][i] += pre[1][i-1];
    }
    dp[0][0][0] = 1;
    for(int k = 0; k<=K; k++){
        for(int i= 0; i<=N; i++){
            for(int b = 0; b<2; b++){
                if(dp[b][k][i]){
                    if(s[i] != 'X'){
                        par[0][k][i+1] = -b;
                        dp[0][k][i+1] = 1;
                    }
                    if(k != K && c[k] + i <= N && pre[0][c[k]+i]-pre[0][i] == 0){
                        par[1][k+1][i+c[k]] = 1;
                        dp[1][k+1][i+c[k]] = 1;
                    }
                }
            }
        }
    }
    string ret;
    int crntb = 0, crntk = K, crntn = N;
    if(dp[1][K][N]){
        crntb = 1;
    }
    while(crntn){
        if(par[crntb][crntk][crntn] == 1){
            int lim = crntn - c[crntk-1];
            while(crntn > lim){
                ret.push_back('X');
                crntn--;
            }
            crntk--;
            crntb ^= 1;
        }
        else if(par[crntb][crntk][crntn] == -1){
            crntb ^= 1;
            crntn--;
            ret.push_back('_');
        }
        else{
            ret.push_back('_');
            crntn--;
        }
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

/*
int main(){
    cout << solve_puzzle("..........", {3, 4}) << endl;
}
*/

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