Submission #720434

#	Time	Username	Problem	Language	Result	Execution time	Memory
720434		thimote75	Paint By Numbers (IOI16_paint)	C++14	100 / 100	902 ms	95564 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;

#define idata vector<int>

idata white_count;
idata block_sizes;
string buffer;

bool can_be_jump (int l, int r) {
    if (l == -1 && white_count[r] == 0)
        return true;
    if (l < 0) return false;
    return white_count[r] == white_count[l] && buffer[l] != 'X';
}

int dp[200001][101];

#define NC 0
#define VALID -2
#define INVALID -1
#define COMPUTED -3

idata is_black;
idata is_white;

void use_black (int l, int r) {
    if (l < 0) return ;
    is_black[l] ++;

    if (r != buffer.size() - 1)
        is_black[r + 1] --;
}
void use_white (int l, int r) {
    if (l < 0) return ;
    is_white[l] ++;

    if (r != buffer.size() - 1)
        is_white[r + 1] --;
}

int compute (int pos, int id_block) {
    if (pos <= -1 && id_block == 0) return VALID;
    if (pos <= -1) return INVALID;
    if (dp[pos][id_block] != NC) return dp[pos][id_block];

    if (buffer[pos] != 'X') dp[pos][id_block] = compute(pos - 1, id_block);
    if (id_block != 0
     && can_be_jump(pos - block_sizes[id_block - 1], pos))
        dp[pos][id_block] = min(
            dp[pos][id_block], 
            compute(pos - block_sizes[id_block - 1] - 1, id_block - 1)
        );

    if (dp[pos][id_block] == NC)
        dp[pos][id_block] = INVALID;

    return dp[pos][id_block];
}
void rebuild (int pos, int id_block) {
    if (pos < 0) return ;
    if (dp[pos][id_block] != VALID) return ;

    if (buffer[pos] != 'X') {
        if (pos == 0) {
            if (id_block == 0)
                use_white(pos, pos);
        } else if (dp[pos - 1][id_block] != INVALID) {
            rebuild(pos - 1, id_block);
            use_white(pos, pos);
        }
    }

    if (id_block != 0
     && can_be_jump(pos - block_sizes[id_block - 1], pos)
     && compute(pos - block_sizes[id_block - 1] - 1, id_block - 1) != INVALID) {
        rebuild(pos - block_sizes[id_block - 1] - 1, id_block - 1);
        use_white(pos - block_sizes[id_block - 1], pos - block_sizes[id_block - 1]);
        use_black(pos - block_sizes[id_block - 1] + 1, pos);
    }

    dp[pos][id_block] = COMPUTED;
}

string solve_puzzle(string _s, idata c) {
    buffer = _s;
    block_sizes = c;

    white_count.resize(buffer.size());
    is_white.resize(buffer.size());
    is_black.resize(buffer.size());
    for (int i = 0; i < buffer.size(); i ++)
        if (_s[i] == '_')
            white_count[i] ++;
    for (int i = 1; i < buffer.size(); i ++)
        white_count[i] += white_count[i - 1];

    compute(buffer.size() - 1, c.size());
    rebuild(buffer.size() - 1, c.size());

    string res;
    int b = 0, w = 0;
    for (int i = 0; i < buffer.size(); i ++) {
        b += is_black[i];
        w += is_white[i];

        if (b != 0 && w != 0) res += "?";
        else if (w != 0) res += "_";
        else res += "X";
    }

    return res;
}

Compilation message (stderr)

paint.cpp: In function 'void use_black(int, int)':
paint.cpp:34:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     if (r != buffer.size() - 1)
      |         ~~^~~~~~~~~~~~~~~~~~~~
paint.cpp: In function 'void use_white(int, int)':
paint.cpp:41:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     if (r != buffer.size() - 1)
      |         ~~^~~~~~~~~~~~~~~~~~~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for (int i = 0; i < buffer.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~
paint.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for (int i = 1; i < buffer.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~
paint.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int i = 0; i < buffer.size(); i ++) {
      |                     ~~^~~~~~~~~~~~~~~

• 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