Submission #1224570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224570		madamadam3	Paint By Numbers (IOI16_paint)	C++20	10 / 100	2095 ms	420 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

#define trace(x) for (auto &el : x) cout << el << " ";

using str = string;
using vi = vector<int>;

const str type[4] = {"X", "_", ".", "?"};
inline int id(char c) {
    if (c == 'X') return 0;
    else if (c == '_') return 1;
    else if (c == '.') return 2;
    else return 3;
}

void output_mask(int n, int mask) {
    for (int bit = 0; bit < n; bit++) {
        cout << (mask & (1 << bit) ? "X" : "_");
    }
    cout << "\n";
}

void trace_bits(int mask, int sf = 16) {
    for (int i = 0; i < sf; i++) {
        if (mask & (1 << i)) cout << "1";
        else cout << "0";
    }
    cout << "\n";
}

str solve_puzzle(str s, vi c) {
    vi base; for (auto &el : s) base.push_back(id(el));

    int n = base.size();
    int k = c.size();

    int is_black = (1 << n) - 1, is_white = (1 << n) - 1;
    for (int mask = 0; mask < (1 << n); mask++) {
        bool valid = true;
        int white_msk = 0, black_msk = 0;
        for (int bit = 0; bit < n; bit++) {
            bool is_set = mask & (1 << bit);
            if (is_set && base[bit] == 1) valid = false;
            if (!is_set && base[bit] == 0) valid = false;

            if (is_set) black_msk |= (1 << bit);
            else white_msk |= (1 << bit);
        }
        
        int cur_size = 0;
        vi sizes;
        for (int bit = 0; bit < n; bit++) {
            bool is_set = mask & (1 << bit);
            if (is_set) cur_size++;
            else if (cur_size != 0) {
                sizes.push_back(cur_size);
                cur_size = 0;
            }
        }
        if (cur_size != 0) sizes.push_back(cur_size);
        if (sizes.size() != k) {
            valid = false;
        } else {
            for (int i = 0; i < k; i++) {
                valid = valid && sizes[i] == c[i];
            }
        }
        
        if (!valid) continue;
        is_black &= black_msk;
        is_white &= white_msk;
    }

    str ans;
    for (int i = 0; i < n; i++) {
        if (is_black & (1 << i) && !(is_white & (1 << i))) ans += "X";
        else if (is_white & (1 << i) && !(is_black & (1 << i))) ans += "_";
        else ans += "?";
    }
    return ans;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10