Submission #1046631

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

messy

#include <bits/stdc++.h>
#include "messy.h"
using namespace std;

typedef long long ll;

vector<int> restore_permutation(int n, int w, int r) {
    string s0 = "", s1 = "";
    for (int i = 0; i < n; i++) {
        s0 += '0';
        s1 += '1';
    }
    string s;
    s = s1; s[n-1] = '0';
    add_element(s);
    s = s1; s[n-2] = '0';
    add_element(s);
    s = s1; s[n-3] = '0';
    add_element(s);
    s = s1; s[n-1] = s[n-2] = '0';
    add_element(s);
    s = s1; s[n-1] = s[n-3] = '0';
    add_element(s);
    s = s1; s[n-2] = s[n-3] = '0';
    add_element(s);
    s = s0; s[n-1] = '1';
    add_element(s);
    s[n-2] = '1';
    add_element(s);

    vector<string> sBits;
    s = s0; s[n-1] = '1';
    sBits.push_back(s);
    s = s0; s[n-2] = '1';
    sBits.push_back(s);
    s = s0; s[n-1] = s[n-2] = '1';
    sBits.push_back(s);
    s = s0; s[n-3] = '1';
    sBits.push_back(s);
    s = s0; s[n-1] = s[n-3] = '1';
    sBits.push_back(s);
    s = s0; s[n-2] = s[n-3] = '1';
    sBits.push_back(s);
    s = s0; s[n-1] = s[n-2] = s[n-3] = '1';
    sBits.push_back(s);
    for (int i = 0; i < n-3; i++) {
        for (int b = 0; b < 7; b++) {
            if ((i >> b) & 1) {
                s = sBits[b];
                s[i] = '1';
                add_element(s);
            }
        }
    }
    compile_set();

    vector<ll> G(n);
    for (int i = 0; i < n; i++) G[i] = i;
    mt19937 mt(time(0));
    shuffle(G.begin(), G.end(), mt);

    vector<int> res(n);
    vector<ll> c(3, -1);
    ll ptr = 0;
    s = s1;
    for (int i1 = 0; i1 < n-1; i1++) {
        int i = G[i1];
        s[i] = '0';
        bool has = check_element(s);
        if (has) {
            c[ptr++] = i;
        }
        if (!has || ptr > 1) {
            s[i] = '1';
        }
        if (ptr == 3) break;
    }
    if (ptr < 3) c[2] = G[n-1];
    s = s0;
    s[c[0]] = '1';
    bool v = check_element(s);
    vector<ll> ctrl(3);
    if (!v) {
        s = s0;
        s[c[1]] = '1';
        v = check_element(s);
        if (!v) {
            ctrl[0] = c[2];
            s = s0;
            s[ctrl[0]] = s[c[0]] = '1';
            v = check_element(s);
            if (!v) {
                ctrl[1] = c[1];
                ctrl[2] = c[0];
            }
            else {
                ctrl[1] = c[0];
                ctrl[2] = c[1];
            }
        }
        else {
            ctrl[0] = c[1];
            s = s0;
            s[ctrl[0]] = s[c[0]] = '1';
            v = check_element(s);
            if (!v) {
                ctrl[1] = c[2];
                ctrl[2] = c[0];
            }
            else {
                ctrl[1] = c[0];
                ctrl[2] = c[2];
            }
        }
    }
    else {
        ctrl[0] = c[0];
        s = s0;
        s[ctrl[0]] = s[c[1]] = '1';
        v = check_element(s);
        if (!v) {
            ctrl[1] = c[2];
            ctrl[2] = c[1];
        }
        else {
            ctrl[1] = c[1];
            ctrl[2] = c[2];
        }
    }
    vector<bool> isCtrl(n);
    isCtrl[ctrl[0]] = true;
    isCtrl[ctrl[1]] = true;
    isCtrl[ctrl[2]] = true;

    sBits.clear();
    s = s0; s[ctrl[0]] = '1';
    sBits.push_back(s);
    s = s0; s[ctrl[1]] = '1';
    sBits.push_back(s);
    s = s0; s[ctrl[0]] = s[ctrl[1]] = '1';
    sBits.push_back(s);
    s = s0; s[ctrl[2]] = '1';
    sBits.push_back(s);
    s = s0; s[ctrl[0]] = s[ctrl[2]] = '1';
    sBits.push_back(s);
    s = s0; s[ctrl[1]] = s[ctrl[2]] = '1';
    sBits.push_back(s);
    s = s0; s[ctrl[0]] = s[ctrl[1]] = s[ctrl[2]] = '1';
    sBits.push_back(s);

    unordered_set<ll> missing;
    for (int i = 0; i < n-3; i++) {
        missing.insert(i);
    }

    shuffle(G.begin(), G.end(), mt);
    for (int i1 = 0; i1 < n; i1++) {
        int i = G[i1];
        if (isCtrl[i]) continue;

        ll val = 0;
        unordered_set<ll> temp = missing;
        for (int b = 6; b >= 0; b--) {
            bool h0 = false, h1 = false;
            for (auto &e : temp) {
                if ((e >> b) & 1) h1 = true;
                else h0 = true;
            }
            if (!h0) {
                val <<= 1;
                val |= 1;
                continue;
            }
            else if (!h1) {
                val <<= 1;
                continue;
            }

            s = sBits[b];
            s[i] = '1';
            v = check_element(s);
            val <<= 1;
            val |= v;
            unordered_set<ll> idk;
            for (auto &e : temp) {
                if (((e >> b) & 1) != v) idk.insert(e);
            }
            for (auto &e : idk) temp.erase(e);
        }
        res[i] = val;
        missing.erase(val);
    }
    res[ctrl[0]] = n-1;
    res[ctrl[1]] = n-2;
    res[ctrl[2]] = n-3;

    return res;
}

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