Submission #469406

#	Time	Username	Problem	Language	Result	Execution time	Memory
469406		luciocf	Paint By Numbers (IOI16_paint)	C++14	7 / 100	1 ms	332 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"

using namespace std;

const int maxn = 2e5+10;

int soma[2][maxn], pref[110];
bool can[2][maxn][110];

int black[maxn], white[maxn];

int get(int l, int r, int q)
{
    return soma[q][r] - soma[q][l-1];
}

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

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

    for (int i = 1; i <= k; i++)
        pref[i] = pref[i-1] + c[i-1];

    for (int j = 0; j <= k; j++)
    {
        can[0][0][0] = 1;

        for (int i = 1; i <= n; i++)
        {
            if (s[i-1] != 'X') can[0][i][j] = can[0][i-1][j];

            if (j < 0 || i < c[j-1] || s[i-c[j-1]] == 'X') continue;

            if (get(i-c[j-1]+1, i, 0) == 0 && get(1, i, 1) <= pref[j] && get(i+1, n, 1) <= pref[k]-pref[j])
                can[0][i][j] |= can[0][max(i-c[j-1]-1, 0)][j-1];
        }
    }

    for (int j = k+1; j >= 1; j--)
    {
        can[1][n+1][k+1] = 1;

        for (int i = n; i >= 1; i--)
        {
            if (s[i-1] != 'X') can[1][i][j] = can[1][i+1][j];

            if (j > k || i+c[j-1] > n+1 || s[i+c[j-1]] == 'X') continue;

            if (j <= k && i+c[j-1] <= n+1 && get(i, i+c[j-1]-1, 0) == 0 && get(1, i-1, 1) <= pref[j-1] && get(i, n, 1) <= pref[k]-pref[j-1])
                can[1][i][j] |= can[1][min(n, i+c[j-1]+1)][j+1];
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            if (s[i-1] == '.' && can[0][i-1][j] && can[1][i+1][j+1])
                white[i] = 1;

            if (j > 0 && i+c[j-1]-1 <= n && get(i, i+c[j-1]-1, 0) == 0 && can[0][max(0, i-2)][j-1] && can[1][min(n+1, i+c[j-1]+1)][j+1])
                black[i]++, black[i+c[j-1]]--;
        }
    }

    for (int i = 1; i <= n; i++)
        black[i] += black[i-1];

    string ans;

    for (int i = 1; i <= n; i++)
    {
        if (s[i-1] == 'X') ans += 'X';
        else if (s[i-1] == '_') ans += '_';
        else if (white[i] && !black[i]) ans += '_';
        else if (!white[i] && black[i]) ans += 'X';
        else ans += '?';
    }

    return ans;
}

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