Submission #108796

#	Time	Username	Problem	Language	Result	Execution time	Memory
108796		tictaccat	Unscrambling a Messy Bug (IOI16_messy)	C++11	100 / 100	7 ms	512 KiB

messy

#include <vector>
#include "messy.h"
#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> p;

void adds(int L, int R) {
    if (L == R) return;
    string guess(n,'1');
    int mid = (L+R)/2;
    for (int i = L; i <= R; i++) guess[i] = '0';
    for (int i = L; i <= mid; i++) {
        guess[i] = '1';
        add_element(guess);
        guess[i] = '0';
    }
     adds(L,mid);
     adds(mid+1,R);
}

void checks(int L, int R, vector<int> go) {

    int k = go.size();
    assert(k == R-L+1);

    if (k == 1) {
        p[go[0]] = L;
        return;
    }

    int mid = (L+R)/2;
    
    string check(n,'1');

    for (int i: go) check[i] = '0';

    vector<int> goL, goR;

    for (int i: go) {
        check[i] = '1';
        if (check_element(check)) goL.push_back(i);
        else goR.push_back(i);
        check[i] = '0';
    }

   // for (int e: goL) cout << e << " "; cout << "\n";

     checks(L,mid,goL);
     checks(mid+1,R,goR);
}

std::vector<int> restore_permutation(int nt, int w, int r) {

    n = nt;
    p.resize(n,-1);

    adds(0,n-1);
    compile_set();

    vector<int> go0(n);
    iota(go0.begin(),go0.end(),0);

    checks(0,n-1,go0);

    return p;

}

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