Submission #170434

#	Time	Username	Problem	Language	Result	Execution time	Memory
170434		cheeheng	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	6 ms	552 KiB

messy

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

/*void add_element(string x);
bool check_element(string x);
void compile_set();*/

bool debug = false;

void add_element2(int s, int e, int n){
    if(s == e){return;}

    int m = (s+e)>>1;
    for(int i = s; i <= m; i ++){
        string x = "";
        for(int j = 0; j < n; j ++){
            if(j < s || j > e || j == i){
                x += '1';
            }else{
                x += '0';
            }
        }
        if(debug){
            printf("%s\n", x.c_str());
        }
        add_element(x);
    }

    add_element2(s, m, n);
    add_element2(m+1, e, n);
}

int ans2[130];

void check_element2(int s, int e, int n, vector<int> possible){
    if(debug){
        printf("check_element2 s=%d e=%d n=%d possible=", s, e, n);
        for(int i = 0; i < (int)possible.size(); i ++){
            printf("%d ", possible[i]);
        }
        printf("\n");
    }
    if(s == e){
        ans2[possible[0]] = s;
        return;
    }

    int m = (s+e)>>1;

    vector<int> possiblepos_1;
    vector<int> possiblepos_2;

    for(int i = 0; i < n; i ++){
        if(binary_search(possible.begin(), possible.end(), i)){
            // this position is what you want to query
            string x;
            for(int j = 0; j < n; j ++){
                if(!binary_search(possible.begin(), possible.end(), j) || j == i){
                    x += '1';
                }else{
                    x += '0';
                }
            }
            if(debug){
                printf("%s\n", x.c_str());
            }
            if(check_element(x)){
                // hit: go to left
                if(debug){
                    printf("s=%d e=%d left: %d\n", s, e, i);
                }
                possiblepos_1.push_back(i);
            }else{
                // miss: go to right
                if(debug){
                    printf("s=%d e=%d right: %d\n", s, e, i);
                }
                possiblepos_2.push_back(i);
            }
        }
    }

    /*if(debug){
        printf("check_element2 s=%d e=%d n=%d possiblepos_1=%d possiblepos_2=%d\n", s, e, n, (int)possiblepos_1.size(),
                (int)possiblepos_2.size());
    }*/

    check_element2(s, m, n, possiblepos_1);
    check_element2(m+1, e, n, possiblepos_2);
}

vector<int> restore_permutation(int _n, int w, int r) {
    int n = _n;
    if(debug){
        printf("Elements to be added\n");
    }
    add_element2(0, n-1, n);

    compile_set();
    if(debug){
        printf("Set compiled successfully\n");
    }

    vector<int> everything;
    for(int i = 0; i < n; i ++){
        everything.push_back(i);
    }

    check_element2(0, n-1, n, everything);

    vector<int> ans;
    for(int i = 0; i < n; i ++){
        ans.push_back(ans2[i]);
    }
    return ans;
}

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