Submission #1224729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224729		madamadam3	Paint By Numbers (IOI16_paint)	C++20	Compilation error	0 ms	0 KiB

paint

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

using namespace std;

using vi = vector<int>;

vector<char> to_base2(int idx) {
    vector<char> answer(3);
    for (int bit = 0; bit < 3; bit++) {
        if (idx & (1 << bit)) {
            answer[bit] = '1';
        } else {
            answer[bit] =  '0';
        }
    }

    return answer;
}

vi restore_permutation(int n, int w, int r) {
    random_device rd;
    mt19937 engine(rd());

    vi indices(n); iota(indices.begin(), indices.end(), 0);
    shuffle(indices.begin(), indices.end(), engine);

    string ZEROS = ""; for (int i = 0; i < n; i++) ZEROS += "0";
    string ONES = ""; for (int i = 0; i < n; i++) ONES += "1";

    string cur = ZEROS;
    for (int idx = 0; idx < 3; idx++) {
        int i = indices[idx];

        cur[i] = '1';
        add_element(cur);
    }

    for (int idx = 3; idx < n; idx++) {
        int i = indices[idx];

        for (int bit = 0; bit < 7; bit++) {
            cur = ONES;
            cur[i] = '0';
            if (!(i & (1 << bit))) continue;
            vector<char> enc = to_base2(bit);
            for (int k = 0; k < 3; k++) {
                cur[indices[k]] = enc[k];
            }
            add_element(cur);
        }
    }

    compile_set();

    vi ans(n, -1);
    string test_str = ZEROS;
    vi lls;
    int R = 0;
    for (int bi = 0; bi < 3; bi++) {
        int bit = indices[bi];
        vi next_indices; for (int i = 0; i < n; i++) if (test_str[indices[i]] == '0' && ans[indices[i]] == -1) next_indices.push_back(indices[i]);

        bool found = false;
        for (int lo = 0; lo < next_indices.size()-1; lo++) {
            int loc = next_indices[lo];
            
            test_str[loc] = '1';
            R++;
            if (check_element(test_str)) {
                ans[loc] = bit;
                found = true;

                lls.push_back(loc);
                break;
            }

            test_str[loc] = '0';
        }

        if (!found) {
            test_str[next_indices.back()] = '1';
            ans[next_indices.back()] = bit;
            lls.push_back(next_indices.back());
        }
    }

    cout << "R: " << R << "\n";
    vi value(n, 0); value[lls[0]] = indices[0]; value[lls[1]] = indices[1]; value[lls[2]] = indices[2];
    set<int> avail; for (int i = 0; i < n; i++) avail.insert(i); for (auto &el : lls) avail.erase(el);
    
    for (int bit = 0; bit<7; bit++) {
        for (int idx = 0; idx < n; idx++) {
            int i = indices[idx];
            if (i == lls[0] || i == lls[1] || i == lls[2]) continue;

            set<int> unq; for (int ik = 0; ik < n; ik++) unq.insert(value[ik]);
            if (unq.size() == n) break;
            
            cur = ONES;
            cur[i] = '0';
            vector<char> enc = to_base2(bit);
            for (int k = 0; k < 3; k++) {
                cur[lls[k]] = enc[k];
            }
            R++;
            if (check_element(cur)) {
                value[i] |= (1 << bit);
            }
        }
    }
    cout << "R: " << R << "\n";

    for (int idx = 0; idx < n; idx++) {
        int i = indices[idx];
        ans[value[i]] = i;
    }
    return value;
}

Compilation message (stderr)

paint.cpp:1:10: fatal error: messy.h: No such file or directory
    1 | #include "messy.h"
      |          ^~~~~~~~~
compilation terminated.
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
      |         ^~~~