Submission #1046602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046602		Zicrus	Unscrambling a Messy Bug (IOI16_messy)	C++17	70 / 100	1 ms	604 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<int> res(n);
    vector<ll> c(3, -1);
    ll ptr = 0;
    s = s1;
    for (int i = 0; i < n-1; i++) {
        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] = 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);
    for (int i = 0; i < n; i++) {
        if (isCtrl[i]) continue;

        ll val = 0;
        for (int b = 6; b >= 0; b--) {
            s = sBits[b];
            s[i] = '1';
            v = check_element(s);
            val <<= 1;
            val |= v;
        }
        res[i] = 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: 0 / 30