Submission #802165

#	Time	Username	Problem	Language	Result	Execution time	Memory
802165		PixelCat	Paint By Numbers (IOI16_paint)	C++14	59 / 100	27 ms	65748 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;

bool dp1[MAXK + 10][MAXN + 10];
bool dp2[MAXK + 10][MAXN + 10];
bool dp[MAXK + 10][MAXN + 10];
int last_white[MAXN + 10];
int last_black[MAXN + 10];
int next_white[MAXN + 10];
int next_black[MAXN + 10];
int tag[MAXN + 10];  // 0 = no, 1 = white, 2 = black, 1|2 = both

string solve_puzzle(string s, vector<int32_t> c) {
    int n = sz(s);
    int k = sz(c);
    memset(dp1, 0, sizeof(dp1));
    memset(dp2, 0, sizeof(dp2));
    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];
    }
    next_white[n + 1] = next_black[n + 1] = n + 1;
    Forr(i, n, 1) {
        if(s[i - 1] == 'X') next_black[i] = i;
        else next_black[i] = next_black[i + 1];
        if(s[i - 1] == '_') next_white[i] = i;
        else next_white[i] = next_white[i + 1];
    }
    
    // debug
    // For(i, 1, n) cerr << last_black[i] << " \n"[i == n];
    // For(i, 1, n) cerr << last_white[i] << " \n"[i == n];
    // For(i, 1, n) cerr << next_black[i] << " \n"[i == n];
    // For(i, 1, n) cerr << next_white[i] << " \n"[i == n];

    // walk from beginning
    dp1[0][0] = 1;
    For(j, 1, k) {
        int len = c[j - 1];
        queue<int> que;
        if(dp1[j - 1][0]) que.emplace(0);
        For(i, 1, n) {
            if(dp1[j - 1][i]) que.emplace(i);
            if(i == len && j == 1 && last_white[i] == 0) {
                dp1[j][i] = 1;
            } else if(i > len && i - last_white[i] >= len && last_black[i - len] != i - len) {
                while(sz(que) && que.front() < last_black[i - 1 - len]) {
                    que.pop();
                }
                if(sz(que) && que.front() < i - len) dp1[j][i] = 1;
            }
        }
    }

    // walk from the end
    dp2[k + 1][n + 1] = 1;
    Forr(j, k, 1) {
        int len = c[j - 1];
        queue<int> que;
        if(dp2[j + 1][n + 1]) que.emplace(n + 1);
        Forr(i, n, 1) {
            if(dp2[j + 1][i]) que.emplace(i);
            if(i == n - len + 1 && j == k && next_white[i] == n + 1) {
                dp2[j][i] = 1;
            } else if(i < n - len + 1 && next_white[i] - i >= len && next_black[i + len] != i + len) {
                while(sz(que) && que.front() > next_black[i + 1 + len]) {
                    que.pop();
                }
                if(sz(que) && que.front() > i + len) dp2[j][i] = 1;
            }
        }
    }

    // merge results
    For(j, 1, k) {
        int len = c[j - 1];
        bool ok = false;
        For(i, len, n) {
            dp[j][i] = (dp1[j][i] && dp2[j][i - len + 1]);
            ok = ok || dp[j][i];
        }
        assert(ok);
    }

    // debug
    // For(j, 0, k + 1) {
    //     For(i, 0, n + 1) {
    //         if(dp[j][i]) cerr << "*";
    //         else cerr << ".";
    //     }
    //     cerr << "\n";
    // }

    // can some cells be black?
    For(j, 1, k) {
        int len = c[j - 1];
        queue<int> que;
        For(i, len, n) if(dp[j][i]) {
            que.emplace(i);
        }
        For(i, 1, n) {
            while(sz(que) && que.front() < i) que.pop();
            if(sz(que) && que.front() < i + len) tag[i] |= 2;
        }
    }

    // can some cells be white?
    For(j, 0, k) {
        int mnl, mxr;
        if(j == 0) {
            mnl = 0;
        } else {
            int len = c[j - 1];
            mnl = len;
            while(!dp[j][mnl]) mnl++;
        }
        if(j == k) {
            mxr = n + 1;
        } else {
            int len = c[j];
            mxr = n;
            while(!dp[j + 1][mxr]) mxr--;
            mxr = mxr - len + 1;
        }
        For(i, mnl + 1, mxr - 1) tag[i] |= 1;
    }

    // report answer
    string ans;
    For(i, 1, n) {
             if(tag[i] == 2 || s[i - 1] == 'X') ans.push_back('X');
        else if(tag[i] == 1 || s[i - 1] == '_') ans.push_back('_');
        else if(tag[i] == 3)                    ans.push_back('?');
    }
    return ans;
}

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