Submission #792855

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

messy

#include "messy.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

vector<int> ans;
void encode(int l,int r,string g){
    if(l==r){
        return;
    }
    int m=(l+r)/2;
    for(int i=l;i<=m;i++){
        auto s=g;
        s[i]='1';
        add_element(s);
    }
    string a=g,b=g;
    for(int i=m+1;i<=r;i++){
        a[i]='1';
    }
    for(int i=l;i<=m;i++){
        b[i]='1';
    }
    encode(l,m,a);
    encode(m+1,r,b);
}
void decode(int l,int r,string g,vector<int> v){
    if(l==r){
        ans[v[0]]=l;
        return;
    }
    int m=(l+r)/2;
    vector<int> c,d;
    string a=g,b=g;
    for(auto h:v){
        auto s=g;
        s[h]='1';
        if(check_element(s)){
            c.push_back(h);
            b[h]='1';
        }
        else{
            d.push_back(h);
            a[h]='1';
        }
    }
    decode(l,m,a,c);
    decode(m+1,r,b,d);
}
vector<int> restore_permutation(int n, int w, int r) {
    encode(0,n-1,string(n,'0'));
    compile_set();
    ans.resize(n);
    vector<int> v(n);
    iota(v.begin(),v.end(),0);
    decode(0,n-1,string(n,'0'),v);
    return ans;
}

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