# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
485246 | couplefire | Unscrambling a Messy Bug (IOI16_messy) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "a.h"
using namespace std;
vector<int> restore_permutation(int n, int w, int r){
for(int siz = n; siz>=2; siz>>=1){
for(int l = 0, r = siz; r<=n; l = r, r += siz){
string s(n, '1');
for(int i = l; i<r; ++i)
s[i] = '0';
for(int i = l; i<(l+r)>>1; ++i){
s[i] = '1';
add_element(s);
s[i] = '0';
}
}
} compile_set();
vector<int> p(n), ans(n);
iota(p.begin(), p.end(), 0);
for(int siz = n; siz>=2; siz>>=1){
for(int l = 0, r = siz; r<=n; l = r, r += siz){
string s(n, '1');
for(int i = l; i<r; ++i)
s[p[i]] = '0';
vector<int> lside, rside;
for(int i = l; i<r; ++i){
s[p[i]] = '1';
if(check_element(s)) lside.push_back(p[i]);
else rside.push_back(p[i]);
s[p[i]] = '0';
}
vector<int> tmp = lside;
tmp.insert(tmp.end(), rside.begin(), rside.end());
for(int i = l; i<r; ++i)
p[i] = tmp[i-l];
}
}
for(int i = 0; i<n; ++i)
ans[p[i]] = i;
return ans;
}