Submission #734088

#	Time	Username	Problem	Language	Result	Execution time	Memory
734088		benjaminkleyn	Paint By Numbers (IOI16_paint)	C++17	100 / 100	623 ms	42652 KiB

paint

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

int n, k;
int W[200001], B[200001];
bool dp[2][200001][101];
// dp[0][i][j] = can we place the first j blocks in the first i spaces?
// dp[1][i][j] = can we place the last j blocks in the last i spaces?

bool white[200001], black[200001];

string solve_puzzle(string s, vector<int> c) 
{
    n = s.size(), k = c.size();

    s = "#" + s + "#";

    c.push_back(0);
    reverse(c.begin(), c.end());
    c.push_back(0);
    reverse(c.begin(), c.end());

    for (int t = 1; t >= 0; t--)
    {
        reverse(s.begin(), s.end());
        reverse(c.begin(), c.end());

        W[0] = B[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            W[i] = W[i-1] + (s[i] == '_');
            B[i] = B[i-1] + (s[i] == 'X');
        }

        for (int i = 0; i <= n; i++)
            dp[t][i][0] = (B[i] == 0);

        for (int j = 1; j <= k; j++)
        {
            for (int i = 0; i < c[j]; i++)
                dp[t][i][j] = false;
            dp[t][c[j]][j] = (j == 1 && W[c[j]] == 0);
            for (int i = c[j] + 1; i <= n; i++)
                if (s[i] == '_')
                    dp[t][i][j] = dp[t][i-1][j];
                else if (s[i] == 'X')
                    dp[t][i][j] = ((s[i-c[j]] != 'X') && dp[t][i-c[j]-1][j-1] && (W[i] - W[i-c[j]] == 0));
                else
                    dp[t][i][j] = (dp[t][i-1][j] || ((s[i-c[j]] != 'X') && dp[t][i-c[j]-1][j-1] && (W[i] - W[i-c[j]] == 0)));
        }
    }

    white[0] = white[n+1] = true;
    black[0] = black[n+1] = false;
    for (int i = 1; i <= n; i++)
        if (s[i] == '_')
            white[i] = true, black[i] = false;
        else if (s[i] == 'X')
            white[i] = false, black[i] = true;
        else
            white[i] = false, black[i] = false;

    // for each cell
    for (int i = 1; i <= n; i++)
        if (s[i] == '.')
        {
            for (int j = 0; j <= k; j++)
                if (dp[0][i-1][j] && dp[1][n-i][k-j])
                {
                    // it can only be white if we can place all blocks to left and right.
                    white[i] = true;
                    break;
                }
        }

    // for each block
    for (int j = 1; j <= k; j++)
    {
        // consider each placement of that block.
        int num_placements = 0, p;
        for (int i = 1; i + c[j] - 1 <= n; i++)
        {
            bool place = true;

            // if there is black to either side, we can't place this block.
            if (!(white[i-1] && white[i+c[j]]))
                place = false;

            // if any of the cells inside this placement are forced white, we can't place it here.
            if (W[i+c[j]-1] - W[i-1] > 0)
                place = false;

            // we must be able to place the first j - 1 blocks to the left 
            if (!((j == 1 && B[i-1] == 0) || (i > 1 && dp[0][i-2][j-1])))
                place = false;

            // and the remaining k - j blocks to the right.
            if (!((j == k && B[n] - B[i+c[j]-1] == 0) || (i < n && dp[1][n-i-c[j]][k-j])))
                place = false;

            if (place)
            {
                for (int l = i; l <= i + c[j] - 1; l++)
                    black[l] = true;
                num_placements++;
                p = i;
            }
        }
        if (num_placements == 1)
        {
            black[p-1] = black[p+c[j]] = false;
            white[p-1] = white[p+c[j]] = true;
        }
    }
    string res = string(n, '?');
    for (int i = 1; i <= n; i++)
        if (black[i] && white[i])
            res[i-1] = '?';
        else if (black[i])
            res[i-1] = 'X';
        else if (white[i])
            res[i-1] = '_';
        else
            res[i-1] = 'F';
    return res;
}

• 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