Submission #226198

#	Time	Username	Problem	Language	Result	Execution time	Memory
226198		VEGAnn	Paint By Numbers (IOI16_paint)	C++14	100 / 100	698 ms	68532 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
#define sz(x) ((int)x.size())
using namespace std;
const int N = 200100;
const int K = 110;
string ans;
int n, k, res[N], ad[N], sf[N];
bool f[N][K][2], ff[N][K];

std::string solve_puzzle(std::string s, std::vector<int> c) {
    s += "_";
    n = sz(s);
    k = sz(c);

    sf[n] = 0;

    for (int i = n - 1; i >= 0; i--)
        sf[i] = sf[i + 1] + bool(s[i] == '_');

    f[0][0][0] = 1;

    for (int i = 0; i < n; i++)
    for (int j = 0; j <= k; j++)
    for (int tp = 0; tp < 2; tp++){
        if (!f[i][j][tp]) continue;

        if (s[i] != 'X')
            f[i + 1][j][0] = 1;

        if (j < k) {
            int len = c[j];

            if (i + len + 1 <= n && sf[i] - sf[i + len] == 0 && s[i + len] != 'X')
                f[i + len + 1][j + 1][1] = 1;
        }
    }

    ff[n + 1][0] = 1;

    for (int i = n + 1; i > 1; i--)
    for (int j = 0; j <= k; j++){
        if (!ff[i][j]) continue;

        if (s[i - 2] != 'X')
            ff[i - 1][j] = 1;

        if (j < k){
            int len = c[k - 1 - j];

            if (i - len - 1 >= 0 && sf[i - len - 1] - sf[i - 1] == 0){
                int pos = i - len - 2;

                if (pos < 0 || s[pos] != 'X')
                    ff[i - len - 1][j + 1] = 1;
            }
        }
    }

    for (int i = 1; i <= n; i++)
        for (int kl = 0; kl <= k; kl++) {
            if ((f[i][kl][0] || f[i][kl][1]) && ff[i][k - kl])
                res[i] = 2;
            if (f[i][kl][1] && ff[i][k - kl]){
                int len = c[kl - 1];
                ad[i - len]++;
                ad[i]--;
            }
        }

    int sm = 0;

    for (int i = 1; i <= n; i++){
        sm += ad[i];

        res[i] |= bool(sm > 0);
    }

    for (int i = 1; i < n; i++){
        if (res[i] == 1)
            ans += "X";
        else if (res[i] == 2)
            ans += "_";
        else ans += "?";
    }

    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