#include <bits/stdc++.h> #include "messy.h" using namespace std; #define pb push_back vector<int>ans; int N; void add(int l,int r,string s){ if(l == r)return; int mid = (l+r)/2; for(int i=l;i<=mid;i++){ s[i] = '1'; //cout<<s<<'\n'; add_element(s); s[i] = '0'; } s = string(N,'0'); for(int i=mid+1;i<=r;i++)s[i] = '1'; add(l,mid,s); s = string(N,'0'); for(int i=l;i<=mid;i++)s[i] = '1'; add(mid+1,r,s); } void solve(int l,int r,vector<int>v,string s){ if(l==r){ ans[l] = v[0]; return; } /* cout<<l<<" "<<r<<'\n'; for(int x:v)cout<<x<<" "; cout<<'\n'; cout<<s<<'\n'; */ vector<int>a,b; int mid = (l+r)/2; for(int x:v){ s[x] = '1'; //cout<<s<<" "<<check_element(s)<<'\n'; if(check_element(s))a.push_back(x); else b.push_back(x); s[x] = '0'; } s = string(N,'0'); for(int x:b)s[x] = '1'; solve(l,mid,a,s); s = string(N,'0'); for(int x:a)s[x] = '1'; solve(mid+1,r,b,s); //a contains what [l,mid] bijects to in p[l,mid] //b the inverse } vector<int> restore_permutation(int _n, int w, int r) { int n = _n; N = _n; ans.resize(n); string s(N,'0'); add(0,n-1,s); compile_set(); vector<int>v(n); for(int i=0;i<n;i++)v[i] = i; solve(0,n-1,v,s); vector<int>p(n); for(int i=0;i<n;i++)p[ans[i]] = i; return p; }