Submission #802311

#	Time	Username	Problem	Language	Result	Execution time	Memory
802311		PixelCat	Paint By Numbers (IOI16_paint)	C++14	100 / 100	132 ms	90712 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