Submission #1068540

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

messy

#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define ROF(i,a,b) for (int i = a; i >= b; i--)
#define pb push_back

string s = ""; int N;
void add(int l, int r){
    //range l,l+1,...,r-1
    if (r-l==1) return;
    int mid = (l+r)/2;
    FOR(i,l,mid){
        s[i]='1'; add_element(s); s[i]='0';
    }
    FOR(i,mid,r) s[i]='1';
    add(l,mid);
    FOR(i,mid,r) s[i]='0';
    FOR(i,l,mid) s[i]='1';
    add(mid,r);
    FOR(i,l,mid) s[i]='0';
}

string t;
vi get(int l, int r, vi p){
    if (r-l==1) return p;
    int sz = (r-l); int mid = (l+r)/2;
    vi L,R;
    FOR(i,0,sz){
        t[p[i]]='1';
        if (check_element(t)){
            L.pb(p[i]);
        }else{
            R.pb(p[i]);
        }
        t[p[i]]='0';
    }
    for (int u : R) t[u]='1';
    L = get(l,mid,L);
    for (int u : R) t[u]='0';
    for (int u : L) t[u]='1';
    R = get(mid,r,R);
    for (int u : L) t[u]='0';
    vi ans = L; FOR(i,0,sz/2) ans.pb(R[i]);
    return ans;
}

vi restore_permutation(int n, int w, int r) {
    N=n;
    FOR(i,0,n) s += "0";
    FOR(i,0,n) t += "0";
    add(0,n);
    compile_set();
    vi p(n); FOR(i,0,n) p[i]=i;
    p = get(0,n,p);
    vi pos(n); FOR(i,0,n) pos[p[i]]=i;
    return pos;
}

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