Submission #1074184

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

messy

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

typedef int ll;

#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(lli = x; i>y; i--)
using namespace std;


ll N;
string idk;
void encode(ll a, ll b){
    if (a==b) return;
    string temp = idk;
    FOR(i,0,N){
        if (!(a<=i && i<=b)) temp[i] = '1';
    }
    ll mid = (a+b)/2;
    FOR(i,a,mid+1){
        temp[i] = '1';
        add_element(temp);

        temp[i] = '0';
    }
    encode(a, mid);
    encode(mid+1, b);
}

vector<ll> solve(set<ll> a){


    if (a.size() == 1){
        vector<ll> ans;
        for (auto&i : a) ans.push_back(i);
        return ans;
    }
    string temp = idk;
    set<ll> temp1, temp2;
    FOR(i,0,N) if (a.count(i)==0) temp[i] = '1';
    
    for (auto&i : a){
        temp[i] = '1';
        
        ll lol = check_element(temp);

        if (lol) temp1.insert(i);
        else temp2.insert(i);
        temp[i] = '0';
    }
    vector<ll> ans1 = solve(temp1);
    vector<ll> ans2 = solve(temp2);
    vector<ll> ans;
    for (auto&i : ans1) ans.push_back(i);
    for (auto&i : ans2) ans.push_back(i);
    return ans;
}

std::vector<int> restore_permutation(int n, int w, int r) {
    N = n;
    FOR(i,0,n) idk += '0';
    encode(0, n-1);
    compile_set();
    set<ll> temp;
    FOR(i,0,n) temp.insert(i);
    vector<ll> ans = solve(temp);
    vector<ll> realans(n);
    FOR(i,0,N){
        realans[ans[i]] = i;
    }
    return realans;


}

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