Submission #922008

#	Time	Username	Problem	Language	Result	Execution time	Memory
922008		Pannda	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	2 ms	856 KiB

messy

#include "messy.h"
using namespace std;
 
vector<int> restore_permutation(int n, int w, int r) {
    int k = 31 - __builtin_clz(n);
    vector<int> p(n, 0);
 
    auto addSubset = [&](vector<int> subset) {
        string s(n, '0');
        for (int i : subset) {
            s[i] = '1';
        }
        add_element(s);
    };
    for (int b = 0; b < k; b++) {
        int mask = (1 << b) - 1;
        for (int base = 0; base < n; base++) {
            if (base >> b & 1) {
                vector<int> subset = { base };
                for (int aug = 0; aug < n; aug++) {
                    if ((aug & mask) != (base & mask)) {
                        subset.push_back(aug);
                    }
                }
                addSubset(subset);
            }
        }
    }
 
    compile_set();
 
    auto checkSubset = [&](vector<int> subset) {
        string s(n, '0');
        for (int i : subset) {
            s[i] = '1';
        }
        return check_element(s);
    };
    for (int b = 0; b < k; b++) {
        int mask = (1 << b) - 1;
        for (int i = 0; i < n; i++) { // here tries to infer the 2^b bit of p[i]
            vector<int> subset = { i };
            for (int j = 0; j < n; j++) {
                if ((p[j] & mask) != (p[i] & mask)) {
                    subset.push_back(j);
                }
            }
            p[i] |= checkSubset(subset) << b;
        }
    }
 
    return p;
}

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