Submission #1208300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208300		omsincoconut	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	1 ms	584 KiB

messy

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

using namespace std;

string popat(int n, vector<int> p) {
    string s(n, '0');
    for (int i : p) s[i] = '1';
    return s;
}

vector<int> restore_permutation(int n, int w, int r) {
    int MAX_BIT = 31-__builtin_clz(n);

    vector<int> popbit[MAX_BIT];
    for (int bit = 0; bit < MAX_BIT; bit++) {
        for (int i = 0; i < n; i++)
            if (i&(1<<bit))
                popbit[bit].push_back(i);
    }

    vector<int> last;
    for (int bit = 0; bit < MAX_BIT; bit++) {
        for (int i : popbit[bit]) {
            vector<int> to_add = last;
            if (find(to_add.begin(), to_add.end(), i) == to_add.end()) to_add.push_back(i);
            else to_add.erase(find(to_add.begin(), to_add.end(), i));
            add_element(popat(n, to_add));
        }
        last = popbit[bit];
    }

    compile_set();

    last = vector<int>();
    vector<int> p(n);
    for (int bit = 0; bit < MAX_BIT; bit++) {
        vector<int> popped;
        for (int i = 0; i < n; i++) {
            vector<int> to_add = last;
            if (find(to_add.begin(), to_add.end(), i) == to_add.end()) to_add.push_back(i);
            else to_add.erase(find(to_add.begin(), to_add.end(), i));
            if (check_element(popat(n, to_add))) {
                p[i] |= (1<<bit);
                popped.push_back(i);
            }
        }

        last = popped;
    }

    return p;
}

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: 30 / 30