Submission #878965

#	Time	Username	Problem	Language	Result	Execution time	Memory
878965		charleehp	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1081 ms	110472 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <iostream>

#define MAX_N 200000
#define MAX_K 100

int n, k;
std::string S;
std::vector<int> C;
int W[MAX_N], B[MAX_N];

bool memoLeft[MAX_N][MAX_K];
bool memoRight[MAX_N][MAX_K];
bool visLeft[MAX_N][MAX_K];
bool visRight[MAX_N][MAX_K];

bool possible[MAX_N][MAX_K];

int whiteInRange(int a, int b) {
    int sum = W[b];
    if (a)
        sum -= W[a - 1];
    return sum;
}

bool noBlacksInRange(int a, int b) {
    int sum = B[b];
    if (a)
        sum -= B[a - 1];
    return sum == 0;
}

bool canPlace(int i, int b) {
    if (i < 0)
        return false;

    // white space before  i
    if (i > 0 && S[i - 1] == 'X')
        return false;

    // all black spaces 
    if (i + C[b] > n)
        return false;

    if (whiteInRange(i, i + C[b] - 1))
        return false;

    // white space after end of block
    if (i <= n - 1 && S[i + C[b]] == 'X')
        return false;

    return true;
}

bool solLeft(int i, int b) {
    if (i >= n) 
        return b == k;
    
    if (b == k)
        return noBlacksInRange(i, n - 1);
    
    if (!visLeft[i][b]) {
        visLeft[i][b] = true;

        if (S[i] == '_') {
            memoLeft[i][b] = solLeft(i + 1, b);
        } else if (S[i] == 'X') {
            memoLeft[i][b] = canPlace(i, b) && solLeft(i + C[b] + 1, b + 1);
        } else {
            memoLeft[i][b] = (solLeft(i + 1, b)) || (canPlace(i, b) && solLeft(i + C[b] + 1, b + 1));
        }
    }
    return memoLeft[i][b];
}

bool solRight(int i, int b) {
    if (i < 0) 
        return b == -1;

    if (b == -1)
        return noBlacksInRange(0, i);
    
    if (!visRight[i][b]) {
        visRight[i][b] = true;

        if (S[i] == '_') {
            memoRight[i][b] = solRight(i - 1, b);
        } else if (S[i] == 'X') {
            memoRight[i][b] = canPlace(i - C[b] + 1, b) && solRight(i - C[b] - 1, b - 1);
        } else {
            memoRight[i][b] = (solRight(i - 1, b)) || (canPlace(i - C[b] + 1, b) && solRight(i - C[b] - 1, b - 1));
        }
    }
    return memoRight[i][b];
}

bool solutionWithBlock(int i, int b) {
    if (!canPlace(i, b))
        return false;
    
    return (solRight(i - 2, b - 1) && solLeft(i + C[b] + 1, b + 1));
}

void fillPossiblePositionsForBlocks() {
    for (int b = 0; b < k; b++) {
        for (int i = 0; i < n; i++) {
            if (solutionWithBlock(i, b)) {
                for (int j = 0; j < C[b]; j++) {
                    possible[i + j][b] = true;
                }
            }
        }
    }
}

bool canBeWhite(int i) {
    if (S[i] == 'X')
        return false;

    for (int b = -1; b < k; b++) {
        if (solRight(i - 1, b) && solLeft(i + 1, b + 1))
            return true;
    }

    return false;
}

bool canBeBlack(int i) {
    if (S[i] == '_')
        return false;

    for (int b = 0; b < k; b++) {
        if (possible[i][b])
            return true;
    }
    return false;
}

std::string solve_puzzle(std::string s, std::vector<int> c) {
    n = s.size();
    k = c.size();
    S = s;
    C = c;

    W[0] = S[0] == '_' ? 1 : 0;
    B[0] = S[0] == 'X' ? 1 : 0;
    for (int i = 1; i < n; i++) {
        W[i] = W[i - 1];
        W[i] += S[i] == '_' ? 1 : 0;
        B[i] = B[i - 1];
        B[i] += S[i] == 'X' ? 1 : 0;
    }

    fillPossiblePositionsForBlocks();
    /*for (int i = 0; i < n; i++) {
        for (int b = 0; b < k; b++) {
            std::cout << possible[i][b] << " ";
        }
        std::cout << "\n";
    }*/

    // ans
    std::string ans = s;

    for (int i = 0; i < n; i++) {
        if (!canBeWhite(i)) {
            ans[i] = 'X';
            continue;
        } 

        if (canBeBlack(i)) {
            ans[i] = '?';
        } else {
            ans[i] = '_';
        }
    }

    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