Submission #1028863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028863		Warinchai	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	4 ms	652 KiB

messy

#include <vector>
#include<bits/stdc++.h>
#include "messy.h"
using namespace std;
vector<int>ans;
int N;
void add(int st,int en,int l,int r){
    if(st==en)return;
    int m=(st+en)/2;
    string pre,suf,mid;
    for(int i=l;i<st;i++)pre=pre+'1';
    for(int i=en+1;i<=r;i++)suf=suf+'1';
    for(int i=st;i<=m;i++){
        mid="";
        for(int j=st;j<=en;j++){
            if(j==i)mid=mid+'1';
            else mid=mid+'0';
        }
        //cout<<pre+mid+suf<<"\n";
        add_element(pre+mid+suf);
    }
    add(st,m,l,r);
    add(m+1,en,l,r);
}
void check(int st,int en,int l,int r,vector<int>pre,vector<int>mid,vector<int>suf){
    //cerr<<st<<' '<<en<<"\n";
    //cerr<<ans.size()<<' '<<mid.size()<<"\n";
    if(st==en)return void(ans[mid[0]]=st-1);
    string s(N,'0');
    int m=(st+en)/2;
    for(auto x:pre)s[x]='1';
    for(auto x:suf)s[x]='1';
    vector<int> npre=pre,nsuf=suf,midl,midr;
    for(auto x:mid){
        s[x]='1';
        //cerr<<s<<"\n";
        if(check_element(s))midl.push_back(x),npre.push_back(x);
        else midr.push_back(x),nsuf.push_back(x);
        s[x]='0';
    }
    check(st,m,l,r,pre,midl,nsuf);
    check(m+1,en,l,r,npre,midr,suf);
}
std::vector<int> restore_permutation(int n, int w, int r) {
    //cerr<<"work\n";
    ans.clear();
    N=n;
    add(1,n,1,n);
    //cerr<<"add work\n";
    compile_set();
    ans.resize(n);
    vector<int>mid;
    for(int i=0;i<n;i++)mid.push_back(i);
    //cerr<<"work\n";
    check(1,n,1,n,vector<int>(),mid,vector<int>());
    //cerr<<"check work\n";
    return ans;
}

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