Submission #537900

#	Time	Username	Problem	Language	Result	Execution time	Memory
537900		timreizin	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1558 ms	139396 KiB

paint

#include "paint.h"

using namespace std;

string solve_puzzle(string s, vector<int> c)
{
    int n = (int)s.size(), k = c.size();
    vector dpWR(n + 1, vector(k + 1, false)), dpBR(n + 1, vector(k + 1, false)), dpWL(n + 2, vector(k + 1, false)), dpBL(n + 2, vector(k + 1, false));
    vector<int> pref(n + 1);
    for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + (s[i] == '_');
    dpWR[0][0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= k; ++j)
        {
            if (s[i - 1] != '_' && j != k && i - c[j] >= 0 && pref[i] - pref[i - c[j]] == 0) dpBR[i][j] = dpWR[i - c[j]][j];
            if (s[i - 1] != 'X') dpWR[i][j] = dpWR[i - 1][j] | (j == 0 ? 0 : dpBR[i - 1][j - 1]);
        }
    }
    dpWL[n + 1][k] = 1;
    for (int i = n; i >= 1; --i)
    {
        for (int j = 0; j <= k; ++j)
        {
            if (s[i - 1] != '_' && j != k && i + c[j] <= n + 1 && pref[i + c[j] - 1] - pref[i - 1] == 0) dpBL[i][j] = dpWL[i + c[j]][j + 1];
            if (s[i - 1] != 'X') dpWL[i][j] = dpWL[i + 1][j] | dpBL[i + 1][j];
        }
    }
    vector<vector<int>> works(k);
    for (int i = 1; i <= n; ++i) for (int j = 0; j < k; ++j) if (i + c[j] - 1 <= n && dpBL[i][j] && dpBR[i + c[j] - 1][j]) works[j].push_back(i);
    for (int i = 1; i <= n; ++i)
    {
        bool checkW = false, checkB = false;
        for (int j = 0; j <= k; ++j)
        {
            checkW |= dpWR[i][j] && dpWL[i][j];
            if (j < k)
            {
                auto it = lower_bound(works[j].begin(), works[j].end(), i + 1 - c[j]);
                if (it != works[j].end()) checkB |= *it <= i;
            }
        }
        if (checkB && checkW) s[i - 1] = '?';
        else if (checkB) s[i - 1] = 'X';
        else s[i - 1] = '_';
    }
    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