Submission #137374

#	Time	Username	Problem	Language	Result	Execution time	Memory
137374		neki	Unscrambling a Messy Bug (IOI16_messy)	C++14	20 / 100	4 ms	504 KiB

messy

#include "messy.h"
#include <bits/stdc++.h>
#define loop(i, a, b) for(int i=a;i<b;i++)
using namespace std;

int n;
vector<int> ans;

void se(int l, int r){
    if(l+1==r) return;
    string ss(n, '1'), can(r-l, '0');
    loop(i, l, (l+r)/2){
        auto ts=ss;ts.replace(l, can.length(), can);
        ts[i]='1';
        add_element(ts);
    }
    se(l, (l+r)/2);se((l+r)/2, r);
}

void guess(int l, int r){
    if(l+1==r) return;
    string ss(n, '1');
    loop(i, l, r) ss[ans[i]]='0';
    vector<int> le, re;
    loop(i, l, r){
        auto ts=ss;
        ts[ans[i]]='1';
        if(check_element(ts)) le.push_back(ans[i]);
        else re.push_back(ans[i]);
    }
    loop(i, l, (l+r)/2) ans[i]=le[i-l];
    loop(i, (l+r)/2, r) ans[i]=re[i-(l+r)/2];
    guess(l, (l+r)/2);guess((l+r)/2, r);
}

vector<int> restore_permutation(int N, int w, int r) {
    n=N;
    se(0, n);
    compile_set();
    ans.resize(n);
    loop(i, 0, n) ans[i]=i;
    guess(0, n);
    return ans;
}

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