제출 #802318

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
802318		PixelCat	Paint By Numbers (IOI16_paint)	C++14	100 / 100	141 ms	90556 KiB

paint

#include "paint.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for (int i = a; i <= b; i++)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
// #define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 200'000;
const int MAXK = 100;

int dp[MAXK + 10][MAXN + 10];
int last_white[MAXN + 10];
int last_black[MAXN + 10];
int owo[MAXN + 10];
int tag[MAXN + 10]; // 0 = no, 1 = white, 2 = black, 1|2 = both

string solve_puzzle(string s, vector<int32_t> c)
{
    s = '_' + s;
    int n = sz(s);
    int k = sz(c);
    memset(dp, 0, sizeof(dp));
    memset(tag, 0, sizeof(tag));

    // build table for next/previous white/black cells
    last_white[0] = last_black[0] = 0;
    For(i, 1, n)
    {
        if (s[i - 1] == 'X')
            last_black[i] = i;
        else
            last_black[i] = last_black[i - 1];
        if (s[i - 1] == '_')
            last_white[i] = i;
        else
            last_white[i] = last_white[i - 1];
    }

    // walk from beginning
    For(i, 0, n)
    {
        if (i && last_black[i] == i)
            break;
        dp[0][i] = 1;
    }
    For(j, 1, k)
    {
        int len = c[j - 1];
        For(i, 1, n)
        {
            if (i >= len &&
                i - last_white[i] >= len &&
                last_black[i - len] != i - len &&
                dp[j - 1][i - len - 1])
            {
                dp[j][i] |= 2;
            }
            if (last_black[i] != i &&
                dp[j][i - 1])
            {
                dp[j][i] |= 1;
            }
        }
    }

    // restore transitions
    dp[k][n] |= 4;
    Forr(j, k, 0)
    {
        int len = j ? c[j - 1] : 0;
        Forr(i, n, 2) if (dp[j][i] & 4)
        {
            if (dp[j][i] & 2)
            {
                dp[j - 1][i - len - 1] |= 4;
                owo[i - len + 1] = max(owo[i - len + 1], len);
                tag[i - len] |= 1;
            }
            if (dp[j][i] & 1)
            {
                dp[j][i - 1] |= 4;
                tag[i] |= 1;
            }
        }
    }

    int now = 0;
    For(i, 1, n)
    {
        now = max(now - 1, owo[i]);
        if (now)
            tag[i] |= 2;
    }

    string ans;
    For(i, 2, n)
    {
        if (tag[i] == 3)
            ans.push_back('?');
        if (tag[i] == 2)
            ans.push_back('X');
        if (tag[i] == 1)
            ans.push_back('_');
    }
    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