Submission #779316

#	Time	Username	Problem	Language	Result	Execution time	Memory
779316		vjudge1	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	3 ms	468 KiB

messy

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

vector<int> ans;


string st(vector<int> s){
    string a;
    for(auto i: s) a+=(char)('0'+i);
    return a;
}

void add(vector<int> s){
   add_element(st(s));
}

int check(vector<int> s){
    return check_element(st(s));
}

void rr(int l, int r, vector<int> a, vector<int> b){


    if(l+1==r){
        ans[a[0]]=l;
        ans[b[0]]=r;
    }
    else if(l<r){
        int n= cn;
        vector<int> t(n), x, y;
        for(auto i: b) t[i]=1;

        for(auto i: a){
            t[i]=1;
            if(check(t)) x.push_back(i);
            else y.push_back(i);
            t[i]=0;
        }


        int mid=(l+r)/2;

        rr(l, mid, x, y);
        x.clear(); y.clear();
        for(auto i: b) t[i]=0;

        for(auto i: a) t[i]=1;


        for(auto i: b){
            t[i]=1;
            if(check(t)) x.push_back(i);
            else y.push_back(i);
            t[i]=0;
        }

        rr(mid+1, r, x, y);
    }
    
}

std::vector<int> restore_permutation(int n, int w, int r) {
    vector<int> s(n), t(n);
     cn=n;

     ans.resize(n);

   for(int i=0; i<n/2; i++){
        s[i]=1; add(s); s[i] = 0;
    }

    for(int i=n/2; i>1; i/=2){
        for(int l=0; l<n; l+=2*i){
            vector<int> t(n, 0);
            

            for(int j=l; j<l+i; j++){
                t[j] = 0;
            }   
            for(int j=l+i; j<l+2*i; j++){
                t[j]=1;
            }
            
            for(int j=l; j<l+i/2; j++){
                t[j] = 1;
                add(t);
                t[j]=0;
            }

            for(int j=l; j<l+i; j++){
                t[j] = 1;
            }   
            for(int j=l+i; j<l+2*i; j++){
                t[j]=0;
            }
            
            for(int j=l+i; j<l+3*i/2; j++){
                t[j] = 1;
                add(t);
                t[j]=0;
            }

        }
    }

    compile_set();
  
    vector<int> a, b;

    for(int i=0; i<n; i++) s[i]=0;

    for(int i=0; i<n; i++){
        s[i]=1;
        if(check(s)) a.push_back(i);
        else b.push_back(i);
        s[i]=0;
    }

   rr(0, n-1, a, b);

    return ans;
}


/*
int main(){
   #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
}*/

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