Submission #302746

#	Time	Username	Problem	Language	Result	Execution time	Memory
302746		dantoh000	Unscrambling a Messy Bug (IOI16_messy)	C++14	49 / 100	3 ms	896 KiB

messy

#include <bits/stdc++.h>
using namespace std;
#include "messy.h"
vector<int> ret;
int n;
void query(int s, int e){
    if (s == e) return;
    string Q(n,'0');
    int m = (s+e)/2;
    for (int i = 0; i < s; i++){
        Q[i] = '1';
    }
    for (int i = e+1; i < n; i++){
        Q[i] = '1';

    }
    for (int i = s; i <= m; i++){
        Q[i] = '1';
        add_element(Q);
        Q[i] = '0';
    }
    query(s,m);
    query(m+1,e);
}
void solve(int s, int e, vector<int> q){
    assert((int)q.size() == e-s+1);
    if (s == e){
        ret[q[0]] = s;
        return;
    }
    string Q(n,'0');
    int ct = 0;
    for (int i = 0; i < n; i++){
        if (q[ct] == i){
            ct++;
        }
        else{
            Q[i] = '1';
        }
    }
    vector<int> Lq, Rq;
    for (auto x : q){
        Q[x] = '1';
        if (check_element(Q)) Lq.emplace_back(x);
        else Rq.emplace_back(x);
        Q[x] = '0';
    }
    int m = (s+e)/2;
    solve(s,m, Lq);
    solve(m+1,e, Rq);
}
vector<int> restore_permutation(int N, int w, int r) {
    n = N;
    ret.resize(n);
    query(0,n-1);
    compile_set();
    vector<int> qinit;
    qinit.resize(n);
    iota(qinit.begin(),qinit.end(),0);
    solve(0,n-1,qinit);
    return ret;
}

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