Submission #1043888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043888		cjoa	Paint By Numbers (IOI16_paint)	C++17	80 / 100	2025 ms	4848 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <vector>
#include <string>

#include <iostream>
#include <cassert>

using namespace std;

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

using VB = vector<bool>;
using VVB = vector<VB>;

const int MAXN = 200000;
const int MAXK = 100;

bool cached[MAXN][MAXK+1];
bool memo[MAXN][MAXK+1];
void reset_DP() {
    for (int i = 0; i < N; i++)
        for (int k = 0; k <= K; k++)
            cached[i][k] = false;
}
bool dp(int n, int k) {
    if (n >= N)
        return k == K;

    if (cached[n][k])
       return memo[n][k];

    bool res = false;
    // start a block of C[k] black cells
    if (k < K and n + C[k] <= N and S[n + C[k]] != 'X') {
        bool ok = true;
        for (int j = 0; j < C[k]; j++) {
            if (S[n + j] == '_') {
                ok = false;
                break;
            }
        }
        if (ok) {
            res = res or dp(n + C[k] + 1, k+1);
        }
    }
    
    // paint cell n white
    if (S[n] != 'X') {
        res = res or dp(n + 1, k);
    }
    
    cached[n][k] = true;
    memo[n][k] = res;
    return res;
}

std::string solve_puzzle(std::string s, std::vector<int> c) {
//  cerr << s << endl;

    N = s.size();
    K = c.size();

    S = s + "_";
    C = c;

    string res = s;

    for (int i = 0; i < N; i++) {
        if (S[i] == '.') {
            S[i] = 'X';
            reset_DP();
            bool can_be_black = dp(0, 0);

            S[i] = '_';
            reset_DP();
            bool can_be_white = dp(0, 0);

         // cerr << "i: " << i << " " << can_be_black << " " << can_be_white << endl;
            assert( can_be_black or can_be_white );
            if (can_be_black and can_be_white)
                res[i] = '?';
            else if (can_be_black)
                res[i] = 'X';
            else
                res[i] = '_';

            S[i] = '.';
       }
    }

    return res;
}

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