Submission #66328

#	Time	Username	Problem	Language	Result	Execution time	Memory
66328		aquablitz11	Paint By Numbers (IOI16_paint)	C++14	100 / 100	378 ms	95072 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
using namespace std;

const char any = '.';
const char white = '_';
const char black = 'X';
const char both = '?';
const int N = 200010;
const int K = 110;

int wqs[N], bqs[N];
bool dp[N][K], pb[N][K], pw[N][K], reach[N][K];

string solve_puzzle(string s, vector<int> c)
{
    int n = s.size();
    int k = c.size();
    s.insert(s.begin(), '\0');
    c.insert(c.begin(), 0);
    for (int i = 1; i <= n; ++i) {
        wqs[i] = wqs[i-1];
        if (s[i] == white)
            ++wqs[i];
    }
    dp[n+1][k+1] = true;
    for (int i = n; i >= 1; --i) {
        for (int j = k+1; j >= 1; --j) {
            if (j <= k && (s[i] == black || s[i] == any)) {
                bool blackstrip = i+c[j]-1 <= n && wqs[i+c[j]-1]-wqs[i-1] == 0;
                bool nextwhite = i+c[j] > n || s[i+c[j]] != black;
                bool nextdp = dp[min(n+1, i+c[j]+1)][j+1];
                if (blackstrip && nextwhite && nextdp) {
                    pb[i][j] = true;
                    dp[i][j] = true;
                }
            }
            if ((s[i] == white || s[i] == any) && dp[i+1][j]) {
                pw[i][j] = true;
                dp[i][j] = true;
            }
            //printf("dp[%d][%d] = %d (W=%d, B=%d)\n", i, j, dp[i][j]?1:0, pw[i][j]?1:0, pb[i][j]?1:0);
        }
    }
    for (int i = 1; i <= n; ++i)
        wqs[i] = 0;

    reach[1][1] = true;
    for (int i = 1; i <= n+1; ++i) {
        for (int j = 1; j <= k+1; ++j) if (reach[i][j] && dp[i][j]) {
            if (pb[i][j]) {
                bqs[i] += 1;
                bqs[i+c[j]] -= 1;
                wqs[i+c[j]] = 1;
                reach[min(n+1, i+c[j]+1)][j+1] = true;
            }
            if (pw[i][j]) {
                wqs[i] = 1;
                reach[i+1][j] = true;
            }
        }
    }

    string ans(n, '\0');
    for (int i = 1; i <= n; ++i) {
        bqs[i] += bqs[i-1];
        if (wqs[i] && bqs[i]) ans[i-1] = both;
        else if (wqs[i]) ans[i-1] = white;
        else ans[i-1] = black;
    }

    return ans;
}

• 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