# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
553338 | fcmalkcin | 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 "gap.h"
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pll pair<ll,ll>
#define ff first
#define ss second
//#define endl "\n"
#define pb push_back
#define F(i,a,b) for(ll i=a;i<=b;i++)
const ll maxn=3e5+100;
const ll base=3e18;
const ll mod= 1e9+7 ;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
ll n;
void dosth(ll l,ll r)
{
if (l==r) return ;
ll mid=(l+r)/2;
for (int t=l;t<=mid;t++)
{
string p;
for (int i=1;i<l;i++) p.pb('1');
for (int i=l;i<=r;i++)
{
if (t==i) p.pb('1');
else p.pb('0');
}
for (int i=r+1;i<=n;i++) p.pb('1');
add_element(p);
}
dosth(l,mid);
dosth(mid+1,r);
}
ll res[maxn];
void dosth1(ll l,ll r,vector<ll> vt)
{
if (l==r)
{
res[vt[0]]=l;
return ;
}
vector<bool> dd(n+3,0);
for (auto to:vt)
{
dd[to]=1;
}
vector<ll> vt1;
vector<ll> vt2;
for (int i=0;i<vt.size();i++)
{
ll x=vt[i];
string p;
for (int i=1;i<=n;i++)
{
if (dd[i])
{
if (i==x)
{
p.pb('1');
}
else
{
p.pb('0');
}
}
else
{
p.pb('1');
}
}
if (check_element(p))
{
vt1.pb(p);
}
else
{
vt2.pb(p);
}
}
dosth1(l,mid,vt1);
dosth1(mid+1,r,vt2);
}
vector<ll> restore_permutation(int n1, int w, int r)
{
n=n1;
dosth(1,n);
compile_set();
vector<ll> vt;
for (int i=1;i<=n;i++) vt.pb(i);
dosth1(1,n,vt);
vector<ll> ans;
for (int i=1;i<=n;i++) ans.pb(p[i]-1);
return ans;
}
/*int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp","r"))
{
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
}
}*/