# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1199104 | pensive | Unscrambling a Messy Bug (IOI16_messy) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
#define ll long long
#define REP(a,i,n) for (ll i=a;i<n;i++)
vector<int> sagot;
void adds(int n, int lo, int hi) {
if (lo==hi) return;
int mid = (lo+hi)/2;
string s = string(n, '1');
REP(lo, i, hi+1) s[i]='0';
REP(lo, i, mid+1) {
s[i]='1';
add_element(s);
s[i] = '0';
}
adds(n, lo, mid); adds(n, mid+1, hi);
}
void solve(int n, vector<int> can, int lo, int hi) {
if (hi-lo==0) {
sagot[lo] = can[0];
return;
}
vector<int> left, right;
string s = string(n, '1');
for (auto u : can) {
s[i] = '0';
}
for (auto u: can) {
s[i]='1';
if (check_element(s)) {
left.push_back(u);
}
else right.push_back(u);
s[i]='0';
}
int mid = (lo+hi)/2;
solve(n, left, lo, mid); solve(n, right, mid+1, hi);
}
vector<int> restore_permutation(int n, int w, int r) {
sagot.resize(n);
adds(n, 0, n-1);
compile_set();
vector<int> cans;
REP(0, i, n) {
cans.push_back(i);
}
solve(n, cans, 0, n-1);
return sagot;
}