Submission #585766

#	Time	Username	Problem	Language	Result	Execution time	Memory
585766		Drew_	Paint By Numbers (IOI16_paint)	C++17	100 / 100	631 ms	33604 KiB

paint

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

const int MAXN = 2e5 + 69;
const int MAXK = 107;

bitset<MAXN> vst[MAXK];
bitset<MAXN> dp[MAXK][2];

int X[MAXN], _[MAXN];
int pfx[2][MAXN];

string solve_puzzle(string s, vector<int> c)
{
    int N = (int)s.size(), K = (int)c.size();
    for (int i = 0; i < N; ++i)
        X[i+1] = X[i] + (s[i] == 'X');
    for (int i = 0; i < N; ++i)
        _[i+1] = _[i] + (s[i] == '_');

    const auto solve = [&](const auto &self, int i, int j) -> bool
    {
        if (j == K)
            return i <= N+1 && (i == N+1 || X[N] - X[i] == 0);
        if (i >= N)
            return false;
        if (vst[j][i]) 
            return dp[j][0][i] || dp[j][1][i];
        vst[j][i] = true;

        if (s[i] != 'X')
            dp[j][0][i] = dp[j][0][i] | self(self, i+1, j);
        if (i + c[j] <= N && _[i + c[j]] - _[i] == 0 && (i + c[j] == N || s[i + c[j]] != 'X'))
            dp[j][1][i] = dp[j][1][i] | self(self, i+c[j]+1, j+1);
        return dp[j][0][i] || dp[j][1][i];
    };
    solve(solve, 0, 0);

    for (int j = 0; j < K; ++j)
    {
        for (int i = 0; i < N; ++i)
        {
            if (dp[j][0][i])
                pfx[0][i]++, pfx[0][i+1]--;
            if (dp[j][1][i])
            {
                pfx[1][i]++;
                pfx[1][i + c[j]]--;
                
                pfx[0][i + c[j]]++;
                if (j+1 < K) pfx[0][i + c[j] + 1]--;
            }
        }
    }

    for (int j = 0; j < 2; ++j)
        for (int i = 1; i < N; ++i)
            pfx[j][i] += pfx[j][i-1];

    for (int i = 0; i < N; ++i)
    {
        if (pfx[0][i] && pfx[1][i])
            s[i] = '?';
        else if (pfx[0][i])
            s[i] = '_';
        else s[i] = 'X';
    }

    return s;
}

• 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