Submission #1018506

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

messy

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

using namespace std;

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

void restore(vector<int>&perm,string s){
    if(perm.size()==1) return;
    vector<int>l,r;
    for(int i:perm){
        s[i]='0';
        if(check_element(s)) l.push_back(i);
        else r.push_back(i);
        s[i]='1';
    }
    for(int i:r) s[i]='0';
    restore(l,s);
    for(int i:r) s[i]='1';
    for(int i:l) s[i]='0';
    restore(r,s);
    swap(perm,l);
    for(int i:r) perm.push_back(i);
}

vector<int> restore_permutation(int n, int w, int r) {
    add(n,0,n);
    compile_set();
    vector<int>perm(n);
    iota(perm.begin(),perm.end(),0);
    restore(perm,string(n,'1'));
    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