Submission #1071543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071543		mc061	Paint By Numbers (IOI16_paint)	C++17	100 / 100	198 ms	83976 KiB

paint

#pragma once
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+6;
const int K = 103;

bool possible[N][K][2]={};
bool backtrack[N][K][2]={};
bool white_poss[N]={};
bool black_poss[N]={};

string solve_puzzle(string s, vector<int> c) {
    const int n = s.size();
    const int k = c.size();
    vector<int> pref_white, pref_black;
    for (int i = 0; i < s.size(); ++i) {
        int prv_w = pref_white.size() ? pref_white.back() : 0;
        int prv_b = pref_black.size() ? pref_black.back() : 0;

        if (s[i] == '_') ++prv_w;
        if (s[i] == 'X') ++prv_b;

        pref_white.push_back(prv_w);
        pref_black.push_back(prv_b);
    }
    possible[0][0][0] = true;
    for (int i = 1; i <= n; ++i) {
        for (int ck = 0; ck <= k; ++ck) {
            if (s[i-1] != 'X') possible[i][ck][0] = possible[i-1][ck][0] | possible[i-1][ck][1];
            if (ck == 0) continue;
            if (s[i-1] == '_') continue;
            if (c[ck-1] > i) continue;
            int r = i;
            int l = i - c[ck-1]+1;
            --r;
            l -= 2;
            int su = pref_white[r];
            if (l >= 0) su -= pref_white[l];
            if (su > 0) continue;
            l++;
            possible[i][ck][1] = possible[l][ck-1][0];
            // cerr << "update " << i << " " << ck << " " << 
        }
    }
    backtrack[n][k][0] = possible[n][k][0];
    backtrack[n][k][1] = possible[n][k][1];

    auto upd_bool = [&] (bool& val, bool new_val) {
        val |= new_val;
    };
    auto assure = [&] (bool& val, bool old) {
        val &= old;
    };

    vector<int> lst_black(k+1, 1e9);
    if (backtrack[n][k][1]) black_poss[n] = true;
    if (backtrack[n][k][0]) white_poss[n] = true;

    for (int i = n-1; i > 0; --i) {
        for (int ck = k; ck >= 0; --ck) {
            bool case1 = backtrack[i+1][ck][0];
            assure(case1, possible[i][ck][0]);
            upd_bool(backtrack[i][ck][0], case1);
            if (ck < k) {
                int le = c[ck];
                bool case2 = backtrack[i+le][ck+1][1];
                assure(case2, possible[i][ck][0]);
                upd_bool(backtrack[i][ck][0], case2);
            }
            if (backtrack[i][ck][0]) {
                white_poss[i] = true;
            }

            if (ck > 0) {
                upd_bool(backtrack[i][ck][1], backtrack[i+1][ck][0]);
                assure(backtrack[i][ck][1], possible[i][ck][1]);
                if (backtrack[i][ck][1]) black_poss[i] = true;
            }
        }
    }
    for (int i = n; i > 0; --i) {
        for (int ck = k; ck > 0; --ck) {
            if (backtrack[i][ck][1]) lst_black[ck] = i;
            if (lst_black[ck] - i + 1 <= c[ck-1]) black_poss[i] = true;
        }
    }
    string ret(n, '0');
    for (int i = 1; i <= n; ++i) {
        if (white_poss[i] && black_poss[i]) ret[i-1] = '?';
        else if (white_poss[i]) ret[i-1] = '_';
        else if (black_poss[i]) ret[i-1] = 'X';
        else assert(false);
    }
    return ret;
}

Compilation message (stderr)

paint.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i = 0; i < s.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