Submission #1224718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224718		madamadam3	Unscrambling a Messy Bug (IOI16_messy)	C++20	70 / 100	1 ms	588 KiB

messy

#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;
    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';

            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());
        }
    }

    vi value(n, 0); value[lls[0]] = indices[0]; value[lls[1]] = indices[1]; value[lls[2]] = indices[2];
    for (int idx = 0; idx < n; idx++) {
        int i = indices[idx];
        if (i == lls[0] || i == lls[1] || i == lls[2]) continue;
        
        for (int bit = 0; bit < 7; bit++) {
            cur = ONES;
            cur[i] = '0';
            vector<char> enc = to_base2(bit);
            for (int k = 0; k < 3; k++) {
                cur[lls[k]] = enc[k];
            }

            if (check_element(cur)) {
                value[i] |= (1 << bit);
            }
        }
    }

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

Compilation message (stderr)

messy.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
messy_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 20 / 20
• Subtask 2: 18 / 18
• Subtask 3: 11 / 11
• Subtask 4: 21 / 21
• Subtask 5: 0 / 30