Submission #1100478

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

messy

#include <vector>
#include <bits/stdc++.h>
#include "messy.h"
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
vector<int> ans;

void dnc1(int l,int r){
    if(l==r)return;
    string s;
    for(int i=0;i<n;i++){
        if(i<l||i>r)s+='1';
        else s+='0';
    }
    int m=(l+r)/2;
    for(int x=l;x<=m;x++){
        s[x]='1';
        add_element(s);
        s[x]='0';
    }
    dnc1(l,m);
    dnc1(m+1,r);
}

void dnc2(vector<int> v,int l,int r){
    if(l==r){
        ans[v[0]]=l;
        return;
    }
    string s;
    for(int i=0;i<n;i++)s+='1';
    for(int x:v)s[x]='0';
    int m=(l+r)/2;
    vector<int> v1,v2;
    for(int x:v){
        s[x]='1';
        if(check_element(s)){
            v1.push_back(x);
        }
        s[x]='0';
    }
    for(int i:v){
        bool b=0;
        for(int j:v1)b|=i==j;
        if(!b)v2.push_back(i);
    }
    dnc2(v1,l,m);
    dnc2(v2,m+1,r);
}

std::vector<int> restore_permutation(int N, int w, int r) {
    n=N;
    ans.resize(n);
    dnc1(0,n-1);
    compile_set();
    vector<int> v(n);
    iota(begin(v),end(v),0);
    dnc2(v,0,n-1);
    return ans;
}

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