Submission #1032262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032262		coolboy19521	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	4 ms	860 KiB

messy

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

using namespace std;

const int sz = 256;

vector<string> qry;
int an[sz];
int n;

map<string,bool> mp;

bool Ask(string s) {
    if (mp.count(s)) return mp[s];
    return mp[s] = check_element(s);
}

void gen_qry(int le, int ri) {
    int mi = le + (ri - le) / 2;
    string p(le - 1, '1');
    string s(n - ri, '1');
    string b(mi - le + 1, '0');
    string f(ri - mi, '0');
    for (int i = le; i <= mi; i ++) {
        b[i - le] = '1';
        qry.push_back(p + b + f + s);
        b[i - le] = '0';
    }
    if (le == ri) return;
    gen_qry(le, mi);
    gen_qry(mi + 1, ri);
}

void solve(int le, int ri, vector<int> bl) {
    if (le == ri) {
        map<int,bool> cn;
        for (int ix : bl) cn[ix];
        for (int i = 0; i < n; i ++) if (!cn.count(i)) an[i] = le - 1;
        return;
    }
    int mi = le + (ri - le) / 2;
    string s(n, '0');
    for (int ix : bl)
        s[ix] = '1';
    vector<int> ls;
    for (int i = 0; i < n; i ++)
        if ('0' == s[i]) {
            s[i] = '1';
            bool f = Ask(s);
            if (!f) bl.push_back(i);
            else ls.push_back(i);
            s[i] = '0';
        }
    solve(le, mi, bl);
    int m = mi - le + 1;
    for (int i = 0; i < m; i ++) bl.pop_back();
    for (int ix : ls) bl.push_back(ix);
    solve(mi + 1, ri, bl);
}

vector<int> restore_permutation(int N, int w, int r) {
    n = N;
    gen_qry(1, n);
    for (auto s : qry)
        add_element(s);
    compile_set();
    solve(1, n, {});
    vector<int> p;
    for (int i = 0; i < n; i ++)
        p.push_back(an[i]);
    return p;
}

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