Submission #593132

#	Time	Username	Problem	Language	Result	Execution time	Memory
593132		Josia	Paint By Numbers (IOI16_paint)	C++14	100 / 100	728 ms	109380 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> blocks;
vector<int> canBeBlack;
vector<int> canBeWhite;
vector<int> blackRequirement;
vector<int> whiteRequirement;


vector<vector<int>> mem;

bool dp(int i, int k) {
    if ((i<0) || (k>0 && i==0)) return 0;
    if (k==0) {
        if (blackRequirement[i] != 0) return 0;

        canBeWhite[0]++;
        canBeWhite[i]--;
        return 1;
    }

    assert(i>0 && k>0);

    if (mem[i][k] != -1) return mem[i][k];

    pair<int, int> nextBlock;   // range (both inclusive)
    nextBlock.second = i-1;
    nextBlock.first = i-blocks[k-1];

    int empty = i-blocks[k-1]-1;


    bool poss = 0;
    if (blackRequirement[i]-blackRequirement[i-1] == 0 && dp(i-1, k)) {
        poss=1;

        canBeWhite[i-1]++;
        canBeWhite[i]--;
    }

    if (nextBlock.first >= 0 && whiteRequirement[nextBlock.second+1]-whiteRequirement[nextBlock.first] == 0) {
        if (empty >= 0 && blackRequirement[empty+1]-blackRequirement[empty] != 0) {
            return mem[i][k] = poss;
        }

        if (nextBlock.first > 0 && (!dp(nextBlock.first-1, k-1))) return mem[i][k] = poss;
        if (nextBlock.first == 0 && k > 1) return mem[i][k] = poss;

        poss = 1;

        if (empty >= 0) {
            canBeWhite[empty]++;
            canBeWhite[empty+1]--;
        }

        canBeBlack[nextBlock.first]++;
        canBeBlack[nextBlock.second+1]--;
    }

    return mem[i][k] = poss;
}



std::string solve_puzzle(std::string s, std::vector<int> c) {

    n = s.size();
    canBeBlack.assign(n+2, 0);
    canBeWhite.assign(n+2, 0);
    blocks = c;

    blackRequirement = {0};
    whiteRequirement = {0};

    for (int i = 0; i<n; i++) {
        blackRequirement.push_back(blackRequirement.back());
        whiteRequirement.push_back(whiteRequirement.back());
        if (s[i] == 'X') blackRequirement.back()++;
        if (s[i] == '_') whiteRequirement.back()++;
    }


    mem.assign(n+2, vector<int>(c.size()+2, -1));
    dp(n, c.size());


    string res;

    int black = 0;
    int white = 0;

    for (int i = 0; i<n; i++) {
        black += canBeBlack[i];
        white += canBeWhite[i];

        if (black && white) res.push_back('?');
        else if (black) res.push_back('X');
        else if (white) res.push_back('_');
        else res.push_back('%');
    }
    

    return res;
}

Compilation message (stderr)

paint.cpp: In function 'bool dp(int, int)':
paint.cpp:49:30: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   49 |             return mem[i][k] = poss;
paint.cpp:52:84: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   52 |         if (nextBlock.first > 0 && (!dp(nextBlock.first-1, k-1))) return mem[i][k] = poss;
paint.cpp:53:61: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   53 |         if (nextBlock.first == 0 && k > 1) return mem[i][k] = poss;
paint.cpp:66:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   66 |     return mem[i][k] = poss;

• 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