Submission #1013096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013096		Mr_Husanboy	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	1 ms	604 KiB

messy

#include <vector>
#include<bits/stdc++.h>

using namespace std;

#include "messy.h"
#define all(a) (a).begin(), (a).end()
template<typename T>
int len(T &a){return a.size();}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());


auto shuffle(vector<int>&a){
    int n = a.size();
    random_shuffle(all(a));
    for(int i = 0; i < n; i ++){
        int ii = rng() % n, jj = rng() % n;
        while(ii == jj) jj = rng() % n;
        swap(a[ii], a[jj]);
    }   

}



void add(int n, int l, int r){
    if(l == r) return;
    string s = string(n, '0');
    for(int i = l; i <= r; i ++) s[i] = '1';
    int m = (l + r) / 2;
    for(int i = l; i <= m; i ++){
        s[i] = '0';
        add_element(s);
        s[i] = '1';
    }
    add(n, l, m);
    add(n, m + 1, r);
}

void restore(vector<int> &perm, string s){
    if(len(perm) == 1) return;
    //for(auto u : perm) cout << u << ' ';
    //cout << endl;
    vector<int> lef, rig;
    for(auto i : perm){
        s[i] = '0';
        if(check_element(s)) lef.push_back(i);
        else rig.push_back(i);
        s[i] = '1';
    }
    //for(auto u : lef) cout << u << ' ';
    // cout << endl;
    for(auto i : rig) s[i] = '0';
    restore(lef, s);
    for(auto i : rig) s[i] = '1';
    for(auto i : lef) s[i] = '0';
    restore(rig, s);
    for(auto i : lef) s[i] = '1';
    perm = lef;
    for(auto i : rig) perm.push_back(i);
}

vector<int> restore_permutation(int n, int w, int r) {
    add(n, 0, n - 1);
    compile_set();
    vector<int> perm(n);
    iota(all(perm), 0);
    string s(n, '1');
    restore(perm, s);
    vector<int> ans(n);
    for(int i = 0; i < n; i ++) ans[perm[i]] = i;
    return ans;
};     

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