Submission #713473

#	Time	Username	Problem	Language	Result	Execution time	Memory
713473		boris_mihov	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1329 ms	99904 KiB

paint

#include "paint.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 200000 + 10;
const int MAXK = 100 + 10;
const int INF  = 1e9;

int n, k;
std::string s;
int lens[MAXK];
bool dp[MAXN][MAXK];
bool bl[MAXN][MAXK];
bool dp2[MAXN][MAXK];
bool bl2[MAXN][MAXK];
int max[MAXN];
int can2[MAXN];
int can[MAXN];

bool f(int pos, int curr)
{
    if (pos >= n) 
    {
        return (curr == k);
    }

    if (bl[pos][curr])
    {
        return dp[pos][curr];
    }

    bl[pos][curr] = true;
    dp[pos][curr] = false;
    if (s[pos] != '_' && curr < k && can[pos] >= lens[curr] && (pos + lens[curr] == n || s[pos + lens[curr]] != 'X'))
    {
        dp[pos][curr] |= f(pos + lens[curr] + 1, curr + 1);
    }

    if (s[pos] != 'X')
    {
        dp[pos][curr] |= f(pos + 1, curr);
    }

    return dp[pos][curr];
}

bool hasX[MAXN];
bool f2(int pos, int curr)
{
    if (pos < 0) 
    {
        return (curr == -1);
    }

    if (curr == -1)
    {
        return !hasX[pos];
    }

    if (bl2[pos][curr])
    {
        return dp2[pos][curr];
    }

    bl2[pos][curr] = true;
    dp2[pos][curr] = false;
    if (s[pos] != '_' && curr < k && can2[pos] >= lens[curr] && (pos - lens[curr] == -1 || s[pos - lens[curr]] != 'X'))
    {
        dp2[pos][curr] |= f2(pos - lens[curr] - 1, curr - 1);
    }

    if (s[pos] != 'X')
    {
        dp2[pos][curr] |= f2(pos - 1, curr);
    }

    return dp2[pos][curr];
}

bool canBeBlack[MAXN];
bool canBeWhite[MAXN];
std::string solve_puzzle(std::string S, std::vector <int> c) 
{
    s = S;
    n = s.size();
    k = c.size();

    for (int i = 0 ; i < k ; ++i)
    {
        lens[i] = c[i];
    }

    for (int i = 0 ; i < n ; ++i)
    {
        hasX[i] = ((i != 0 && hasX[i - 1]) || s[i] == 'X');
        if (s[i] == '_') can2[i] = 0;
        else if (i == 0) can2[i] = 1;
        else can2[i] = can2[i - 1] + 1;
    }

    for (int i = n - 1 ; i >= 0 ; --i)
    {
        if (s[i] == '_') can[i] = 0;
        else can[i] = can[i + 1] + 1;
    }

    for (int i = 0 ; i < n ; ++i)
    {
        if (s[i] == 'X') continue;
        for (int j = 0 ; j <= k ; ++j)
        {
            if (f2(i - 1, j - 1) && f(i + 1, j))
            {
                canBeWhite[i] = true;
            }        
        }
    }

    for (int i = 0 ; i < n ; ++i)
    {
        if (s[i] == '_' || (i > 0 && s[i - 1] == 'X')) continue;
        for (int j = 0 ; j < k ; ++j)
        {
            if (f2(i - 2, j - 1) && can[i] >= lens[j] && i + lens[j] <= n && (i + lens[j] == n || s[i + lens[j]] != 'X') && f(i + lens[j] + 1, j + 1))
            {
                max[i] = std::max(max[i], lens[j]);
            }       
        }
    }

    int left = 0;   
    for (int i = 0 ; i < n ; ++i)
    {
        left = std::max(left - 1, max[i]);
        if (left > 0) canBeBlack[i] = true;
    }

    std::string ans;
    ans.resize(n);

    for (int i = 0 ; i < n ; ++i)
    {
        if (canBeBlack[i] && canBeWhite[i]) ans[i] = '?';
        else if (canBeBlack[i]) ans[i] = 'X';
        else if (canBeWhite[i]) ans[i] = '_';
        else assert(false);
    }

    return ans;
}

• 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