Submission #486354

#	Time	Username	Problem	Language	Result	Execution time	Memory
486354		alextodoran	Paint By Numbers (IOI16_paint)	C++17	100 / 100	361 ms	183140 KiB

paint

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

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

using namespace std;

typedef long long ll;

const int N_MAX = 200000;
const int K_MAX = 100;

int cntB[N_MAX + 2];
int cntW[N_MAX + 2];

int cntSeg (int vec[], int l, int r)
{
    return vec[r] - vec[l - 1];
}

bool pref[N_MAX + 2][K_MAX + 2];
bool suff[N_MAX + 2][K_MAX + 2];

bool prefOr[N_MAX + 2][K_MAX + 2];
bool suffOr[N_MAX + 2][K_MAX + 2];

bool block[N_MAX + 2][K_MAX + 2];

int cntBlock[N_MAX + 2][K_MAX + 2];

bool B[N_MAX + 2];
bool W[N_MAX + 2];

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

    for(int i = 1; i <= N; i++)
    {
        cntB[i] = cntB[i - 1] + (s[i - 1] == 'X');
        cntW[i] = cntW[i - 1] + (s[i - 1] == '_');
    }

    pref[0][0] = true;
    prefOr[0][0] = true;
    for(int i = 1; i <= N; i++)
        for(int j = 0; j <= K; j++)
        {
            pref[i][j] = false;
            if(1 <= j)
            {
                int len = c[j - 1];
                if(i - len + 1 >= 1
                   && cntSeg(cntW, i - len + 1, i) == 0
                   && (i - len == 0 || s[(i - len) - 1] != 'X'))
                    pref[i][j] |= prefOr[max(0, i - len - 1)][j - 1];
            }
            prefOr[i][j] = pref[i][j];
            if(s[i - 1] != 'X')
                prefOr[i][j] |= prefOr[i - 1][j];
        }
    suff[N + 1][K + 1] = true;
    suffOr[N + 1][K + 1] = true;
    for(int i = N; i >= 1; i--)
        for(int j = K + 1; j >= 1; j--)
        {
            suff[i][j] = false;
            if(j <= K)
            {
                int len = c[j - 1];
                if(i + len - 1 <= N
                   && cntSeg(cntW, i, i + len - 1) == 0
                   && (i + len == N + 1 || s[(i + len) - 1] != 'X'))
                    suff[i][j] |= suffOr[min(N + 1, i + len + 1)][j + 1];
            }
            suffOr[i][j] = suff[i][j];
            if(s[i - 1] != 'X')
                suffOr[i][j] |= suffOr[i + 1][j];
        }

    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= K; j++)
        {
            if(i == N)
                block[i][j] = (pref[i][j] & (j == K));
            else if(s[(i + 1) - 1] != 'X')
                block[i][j] = (pref[i][j] & suffOr[i + 2][j + 1]);
            cntBlock[i][j] = cntBlock[i - 1][j] + block[i][j];
        }

    for(int i = 1; i <= N; i++)
    {
        if(s[i - 1] == '_')
        {
            W[i] = true;
            continue;
        }
        if(s[i - 1] == 'X')
        {
            W[i] = false;
            continue;
        }
        for(int j = 0; j <= K; j++)
            W[i] |= (prefOr[i - 1][j] & suffOr[i + 1][j + 1]);
    }
    for(int i = 1; i <= N; i++)
    {
        if(s[i - 1] == 'X')
        {
            B[i] = true;
            continue;
        }
        if(s[i - 1] == '_')
        {
            B[i] = false;
            continue;
        }
        for(int j = 1; j <= K; j++)
            B[i] |= (cntBlock[min(N, i + c[j - 1] - 1)][j] - cntBlock[i - 1][j] > 0);
    }

    string answer;
    for(int i = 1; i <= N; i++)
    {
        if(W[i] == true && B[i] == true)
            answer += '?';
        else if(W[i] == true)
            answer += '_';
        else
            answer += 'X';
    }
    return answer;
}

• 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