Submission #849659

#	Time	Username	Problem	Language	Result	Execution time	Memory
849659		abcvuitunggio	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;
string s;
vector <int> p,v,res;
string add(string s, int l, int r){
    for (int i=l;i<=r;i++)
        s[i]='1';
    return s;
}
void dnc(int l, int r, string s){
    if (l==r)
        return;
    int mid=(l+r)>>1;
    for (int i=l;i<=mid;i++){
        s[i]='1';
        add_element(s);
        s[i]='0';
    }
    dnc(l,mid,add(s,mid+1,r));
    dnc(mid+1,r,add(s,l,mid));
}
string add(string s, vector <int> v){
    for (int i:v)
        s[i]='1';
    return s;
}
void dnc2(int l, int r, vector <int> v, string s){
    if (l==r){
        p.push_back(v[0]);
        return;
    }
    vector <int> L,R;
    for (int i:v){
        s[i]='1';
        if (check_element(s))
            L.push_back(i);
        else
            R.push_back(i);
        s[i]='0';
    }
    int mid=(l+r)>>1;
    dnc2(l,mid,L,add(s,R));
    dnc2(mid+1,r,R,add(s,L));
}
vector <int> restore_permutation(int n, int w, int r){
    for (int i=0;i<n;i++){
        s+='0';
        v.push_back(i);
    }
    dnc(0,n-1,s);
    compile_set();
    dnc2(0,n-1,v,s);
    res.resize(n);
    for (int i=0;i<n;i++)
        res[p[i]]=i;
    return res;
}

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