Submission #1074512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074512		Hugo1729	Unscrambling a Messy Bug (IOI16_messy)	C++11	100 / 100	4 ms	644 KiB

messy

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

int N;

vector<int> t[256];

string make_string(vector<int> bits){
    string s;
    for(int i=0;i<N;i++){
        if(bits[i])s+="1";
        else s+="0";
    }
    return s;
}

void initialize(int v, int tl, int tr){
    if(v<N){
        vector<int> node(N,1);

        // cout << '\n' << v << ' ' << tl << ' ' << tr << '\n';

        for(int i=1;i<=N;i++){
            if(i>=tl&&i<=tr)node[i-1]=0;
        }

        int mid=(tl+tr)/2;

        for(int i=tr;i>mid;i--){
            node[i-1]=1;

            add_element(make_string(node));
            // cout << make_string(node) <<'\n';

            node[i-1]=0;
        }

            // if(tl==tr){
            //     node[tl]=1;

            //     add_element(make_string(node));
            //     cout << make_string(node) <<'\n';
            // }
    }

    if(tl!=tr){
        int mid=(tl+tr)/2;
        initialize(v*2,tl,mid);
        initialize(v*2+1,mid+1,tr);
    }
}

void search(int v, int tl, int tr){
    // cout << '\n' << v << ' ' << tl << ' ' << tr << '\n';
    // for(int i : t[v])cout << i << ' ';
    // cout << '\n';
    if(v<N){
        vector<int> node(N,1);

        for(int i : t[v]){
            node[i]=0;
        }

        int mid=(tl+tr)/2;

        for(int i : t[v]){
            node[i]=1;

            // cout << make_string(node) << ' ' << check_element(make_string(node)) << '\n';

            if(check_element(make_string(node))){
                t[v*2+1].push_back(i);
            }else{
                t[v*2].push_back(i);
            }

            // cout << make_string(node) <<'\n';

            node[i]=0;
        }

            // if(tl==tr){
            //     node[tl]=1;

            //     add_element(make_string(node));
            //     cout << make_string(node) <<'\n';
            // }
    }

    if(tl!=tr){
        int mid=(tl+tr)/2;
        search(v*2,tl,mid);
        search(v*2+1,mid+1,tr);
    }
}

vector<int> restore_permutation(int n, int w, int r) {
    // check_element(make_string(query))
    // add_element(make_string(strings));
    // compile_set();

    N=n;

    initialize(1,1,n);

    compile_set();

    for(int i=0;i<n;i++)t[1].push_back(i);

    search(1,1,n);



    vector<int> p(n,0);

    for(int v=n;v<2*n;v++)p[t[v][0]]=v-n;

    return p;
}

Compilation message (stderr)

messy.cpp: In function 'void search(int, int, int)':
messy.cpp:65:13: warning: unused variable 'mid' [-Wunused-variable]
   65 |         int mid=(tl+tr)/2;
      |             ^~~

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