Submission #752683

#	Time	Username	Problem	Language	Result	Execution time	Memory
752683		puppy	Paint By Numbers (IOI16_paint)	C++17	100 / 100	830 ms	188012 KiB

paint

#include "paint.h"
using namespace std;
bool dp[4][200005][105];
bool dp2[200005][105];
int last2[200005][105];
int last[2][200005];

inline bool query(int l, int r, bool x)
{
    return r < last[x][l] ? false : true;
}
inline bool query2(int l, int r, int j)
{
    return last2[l][j] <= r ? true : false;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
    int N = s.size();
    int K = c.size();
    int cur[2] = {N, N};
    for (int i = N - 1; i >= 0; i--) {
        if (s[i] == '_') cur[0] = i;
        if (s[i] == 'X') cur[1] = i;
        last[0][i] = cur[0], last[1][i] = cur[1];
    }
    for (int i = 0; i < N; i++) {
        if (s[i] == 'X') break;
        dp[1][i][0] = true;
    }
    if (s[0] != '_' && c[0] == 1) dp[0][0][1] = true;
    for (int i = 1; i < N; i++) {
        if (s[i] != 'X') {
            for (int j = 1; j <= K; j++) {
                dp[1][i][j] = dp[1][i-1][j] | dp[0][i-1][j];
            }
        }
        for (int j = 1; j <= K; j++) {
            if (i >= c[j-1] - 1 && !query(i - c[j-1] + 1, i, 0)) {
                if (i == c[j-1] - 1) dp[0][i][j] = j == 1 ? true : false;
                else dp[0][i][j] = dp[1][i-c[j-1]][j-1];
            }
        }
    }
    for (int i = N - 1; i >= 0; i--) {
        if (s[i] == 'X') break;
        dp[3][i][K+1] = true;
    }
    if (s[N-1] != '_' && c[K-1] == 1) dp[2][N-1][K] = true;
    for (int i = N - 2; i >= 0; i--) {
        if (s[i] != 'X') {
            for (int j = 1; j <= K; j++) {
                dp[3][i][j] = dp[2][i+1][j] | dp[3][i+1][j];
            }
        }
        for (int j = 1; j <= K; j++) {
            if (i + c[j-1] - 1 < N && !query(i, i + c[j-1] - 1, 0)) {
                if (i + c[j-1] == N) dp[2][i][j] = j == K ? true : false;
                else dp[2][i][j] = dp[3][i+c[j-1]][j+1];
            }
        }
    }
    string ans = "";
    for (int j = 1; j <= K; j++) {
        for (int i = 0; i < N; i++) {
            if (i + c[j-1] - 1 >= N) break;
            dp2[i][j] = dp[0][i+c[j-1]-1][j] & dp[2][i][j];
        }
    }
    for (int j = 1; j <= K; j++) {
        int cur = N;
        for (int i = N - 1; i >= 0; i--) {
            if (dp2[i][j]) cur = i;
            last2[i][j] = cur;
        }
    }
    for (int i = 0; i < N; i++) {
        if (s[i] == 'X') {
            ans += 'X';
            continue;
        }
        if (s[i] == '_') {
            ans += '_';
            continue;
        }
        bool ok[2] = {};
        for (int j = 0; j <= K; j++) {
            ok[0] |= dp[1][i][j] & dp[3][i][j+1];
        }
        for (int j = 1; j <= K; j++) {
            ok[1] |= query2(max(0, i - c[j-1] + 1), i, j);
        }
        if (ok[0] ^ ok[1]) {
            ans += ok[0] ? '_' : 'X';
        }
        else ans += '?';
    }
    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