Submission #732945

#	Time	Username	Problem	Language	Result	Execution time	Memory
732945		benjaminkleyn	Paint By Numbers (IOI16_paint)	C++17	10 / 100	2082 ms	284 KiB

paint

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

int n, k;
int W[101], B[101];

bool white[101], black[101];

string cur;
void solve(int r, int i, string &s, vector<int> &c, int suff_sum)
{
    if (i == k)
    {
        for (int j = 1; j <= n; j++)
            if (cur[j] == 'X')
                black[j] = true;
            else if (cur[j] == '_')
                white[j] = true;
        return;
    }
    for (int j = r + 2; j + suff_sum - 1 <= n; j++)
        if (W[j + c[i] - 1] - W[j - 1] == 0 && (B[j - 1] - B[r] == 0 || (r == -1 && B[j-1] == 0)))
        {
            for (int m = j; m <= j + c[i] - 1; m++)
                cur[m] = 'X';
            solve(j + c[i] - 1, i + 1, s, c, suff_sum - c[i]);
            for (int m = j; m <= j + c[i] - 1; m++)
                cur[m] = '_';
        }
}

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

    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');
    }

    memset(white, false, sizeof(white));
    memset(black, false, sizeof(black));

    cur = "#" + string(n, '_');

    int sum = 0;
    for (int i = 0; i < k; i++)
        sum += c[i];

    solve(-1, 0, s, c, sum);

    string res = "";
    for (int i = 1; i <= n; i++)
    {
        if (white[i] && black[i])
            res += "?";
        else if (white[i])
            res += "_";
        else if (black[i])
            res += "X";
        else
            res += "F";
    }
    return res;
}

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