Submission #1021897

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

messy

#include <bits/stdc++.h>
#define ent '\n'

typedef long long ll;
using namespace std;
const int maxn = 2e5+12;

void add_element(std::string x);
bool check_element(std::string x);
void compile_set();

int per[maxn];

void rec(vector<int> a, int b, int n){
    if(a.size() == 1) return;
    vector<int> l, r;
    string s0 = "", s1 = "";
    for(int i=0;i<n;i++){
        bool ok = 0;
        for(int x:a){
            if(x == i){
                ok = 1;
            }
        }
        if(!ok){
            s0 += '0';
            s1 += '1';
        }
        else{
            s0 += '1';
            s1 += '0';
        }
    }
    for(int x:a){
        if(!(x & (1 << b))){
            s0[x] = '0';
            add_element(s0);
            l.push_back(x);
            s0[x] = '1';
        }
        else r.push_back(x);
    }
    rec(l, b-1, n);
    rec(r, b-1, n);
}

void find(vector<int> a, int b, int n, int val){
    if(b < -1) return;
    if(a.size() == 1){
        per[a[0]] = val;
        return;
    }
    vector<int> l, r;
    string s0 = "";
    for(int i=0;i<n;i++){
        bool ok = 0;
        for(int x:a){
            if(x == i){
                ok = 1;
            }
        }
        s0 += '0' + ok;
    }
    for(int x:a){
        s0[x] = '0';
        if(check_element(s0)){
            l.push_back(x);
        }
        else{
            r.push_back(x);
        }
        s0[x] = '1';
    }
    find(l, b-1, n, val);
    find(r, b-1, n, val + (1 << b));
}

std::vector<int> restore_permutation(int n, int w, int r){
    vector<int> a;
    for(int i=0;i<n;i++){
        a.push_back(i);
    }
    int b = 0;
    while((1 << (b + 1)) < n){
        b++;
    }
    rec(a, b, n);
    compile_set();
    find(a, b, n, 0);
    vector<int> ans(per, per+n);
    return ans;
}

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