Submission #1070476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070476		Zicrus	Paint By Numbers (IOI16_paint)	C++17	100 / 100	365 ms	34388 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
using namespace std;

typedef long long ll;

ll n, k;
vector<ll> sumW;
vector<vector<bool>> possL, possR;

bool getPossL(int i, int j) {
    if (i < 0) return j == 0;
    return possL[i][j];
}

bool getPossR(int i, int j) {
    if (i >= n) return j == 0;
    return possR[i][j];
}

string solve_puzzle(string s, vector<int> c) {
    n = s.size(), k = c.size();
    sumW = vector<ll>(n+1);
    for (int i = 1; i <= n; i++) sumW[i] = sumW[i-1] + (s[i-1] == '_');
    possL = vector<vector<bool>>(n, vector<bool>(k+1));
    possR = vector<vector<bool>>(n, vector<bool>(k+1));
    possL[0][0] = s[0] != 'X';
    for (int i = 1; i < n; i++) {
        possL[i][0] = possL[i-1][0] && s[i] != 'X';
    }
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= k; j++) {
            possL[i][j] = s[i] != 'X' && getPossL(i-1, j);
            if (i+1-c[j-1] < 0) continue;
            possL[i][j] = possL[i][j] || ((sumW[i+1] - sumW[i+1-c[j-1]] == 0) && (i-c[j-1] < 0 || s[i-c[j-1]] != 'X') && getPossL(i-1-c[j-1], j-1));
        }
    }
    possR[n-1][0] = s[n-1] != 'X';
    for (int i = n-2; i >= 0; i--) {
        possR[i][0] = possR[i+1][0] && s[i] != 'X';
    }
    for (int i = n-1; i >= 0; i--) {
        for (int j = 1; j <= k; j++) {
            possR[i][j] = s[i] != 'X' && getPossR(i+1, j);
            if (i-1+c[k-j] >= n) continue;
            possR[i][j] = possR[i][j] || ((sumW[i+c[k-j]] - sumW[i] == 0) && (i+c[k-j] >= n || s[i+c[k-j]] != 'X') && getPossR(i+1+c[k-j], j-1));
        }
    }

    vector<ll> resB(n+1), resW(n+1);
    for (int j = 0; j < k; j++) {
        for (int i = 0; i+c[j] < n+1; i++) {
            if (sumW[i+c[j]] - sumW[i] != 0) continue;
            if (i-1 >= 0 && s[i-1] == 'X') continue;
            if (i+c[j] < n && s[i+c[j]] == 'X') continue;
            if (!getPossL(i-2, j) || !getPossR(i+1+c[j], k-j-1)) continue;
            resB[i]++; resB[i+c[j]]--;
        }
    }
    for (int i = 1; i < n; i++) resB[i] += resB[i-1];
    for (int j = 0; j <= k; j++) {
        for (int i = 0; i < n; i++) {
            if (s[i] == 'X') continue;
            if (!getPossL(i-1, j) || !getPossR(i+1, k-j)) continue;
            resW[i] = 1;
        }
    }

    string res;
    for (int i = 0; i < n; i++) {
        if (resB[i] > 0 && resW[i] > 0) res.push_back('?');
        else if (resB[i] > 0) res.push_back('X');
        else if (resW[i] > 0) res.push_back('_');
    }
    return res;
}

• 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