Submission #1224737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224737		madamadam3	Paint By Numbers (IOI16_paint)	C++20	59 / 100	0 ms	328 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();

    auto is_fine = [&](int l, int r) {
        bool valid = true;
        for (int idx = l; idx <= r; idx++) {
            valid = valid && base[idx] != 1;
        }
        return valid;
    };

    auto max_fine = [&](int x) {
        int toi = 0;
        int xl = x-1, xr = x;
        while (xr < n && base[xr] != 1) {
            toi++;
            xr++;
        }
        while (xl > 0 && base[xl] != 1) {
            toi++;
            xl--;
        }
        return toi;
    };

    vector<bool> is_black(n, false), is_white(n, false);
    vi min_pos(k, 0), max_pos(k, n - 1);

    for (int i = 0; i < k; i++) {
        min_pos[i] = i == 0 ? 0 : min_pos[i-1] + c[i-1] + 1;
        while (!is_fine(min_pos[i], min_pos[i] - 1 + c[i])) min_pos[i]++;

        for (int px = min_pos[i] + c[i]; px < n; px++) {
            if (base[px] != 0) continue;
            if (i < k - 1 && max_fine(px) >= c[i+1]) break;
            while (px - min_pos[i] + 1 > c[i] || !is_fine(min_pos[i], px)) min_pos[i]++;
            break;
        }
    }

    for (int i = k - 1; i >= 0; i--) {
        max_pos[i] = i == k-1 ? n-1 : max_pos[i+1] - c[i+1] - 1;
        while (!is_fine(max_pos[i] - c[i]+1, max_pos[i])) max_pos[i]--;

        for (int px = max_pos[i] - c[i]; px >= 0; px--) {
            if (base[px] != 0) continue;
            if (i > 0 && max_fine(px) >= c[i-1]) break;
            while (max_pos[i] - px + 1 > c[i] || !is_fine(px, max_pos[i])) max_pos[i]--;
            break;
        }
    }
    
    vector<bool> touched(n, false);
    for (int i = 0; i < k; i++) {
        int L = max_pos[i] - c[i] + 1, R = min_pos[i] + c[i] - 1;

        for (int j = min_pos[i]; j <= max_pos[i]; j++) {
            if (base[j] == 1) continue;
            int cl = j, cr = j;
            while (cl > 0 && base[cl-1] != 1) cl--;
            while (cr < n - 1 && base[cr+1] != 1) cr++;
            if (cr - cl + 1 >= c[i]) touched[j] = true;
        }

        if (L > R) continue;

        for (int j = L; j <= R; j++) {
            is_black[j] = true;
        }
    }

    for (int i = 0; i < k - 1; i++) {
        for (int j = max_pos[i]+1; j < min_pos[i+1]; j++) {
            is_white[j] = true;
        }
    }

    for (int i = 0; i < n; i++) {
        if (!touched[i]) is_white[i] = true;
    }

    str ans;
    for (int i = 0; i < n; i++) {
        if (is_black[i] && !(is_white[i])) ans += "X";
        else if (is_white[i] && !(is_black[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: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10