#include "perm.h"
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>
using namespace std;
typedef long long ll;
int get_nr_bits(ll x)
{
if (x == 0)
{
return 0;
}
assert(x >= 1);
return get_nr_bits(x / 2) + x % 2;
}
vector<int> normalize(vector<int> v)
{
map<int, int> mp;
for (auto& x : v)
{
mp[x] = 0;
}
int y = 0;
for (auto& it : mp)
{
it.second = y++;
}
for (auto& x : v)
{
x = mp[x];
}
return v;
}
vector<int> construct_permutation(ll total)
{
if (total == 1)
{
return {};
}
vector<int> perm;
while (1)
{
int sz = (int)perm.size();
int next_sz = 1 + sz;
if ((1LL << next_sz) <= total)
{
perm.push_back(sz);
}
else
{
break;
}
}
int curval = (int)1e9 + 7;
ll cur = (1LL << (int)perm.size());
while (cur < total)
{
for (int i = (int)perm.size() - 1; i >= -1; i--)
{
int small = 0;
for (int j = 0; j <= i; j++)
{
small += (perm[j] <= 100);
}
if (small != i + 1)
{
continue;
}
if (cur + (1LL << small) <= total)
{
cur += (1LL << small);
vector<int> nperm;
for (int j = 0; j <= i; j++)
{
nperm.push_back(perm[j]);
}
nperm.push_back(curval++);
for (int j = i + 1; j < (int)perm.size(); j++)
{
nperm.push_back(perm[j]);
}
perm = nperm;
break;
}
}
}
assert(cur == total);
perm = normalize(perm);
return perm;
for (auto& p : perm)
{
cout << p << " ";
}
exit(0);
for (int k = 1; 1; k++)
{
ll rem = total + (k - 1);
int nr_bits = get_nr_bits(rem);
if (k < nr_bits)
{
continue;
}
if (rem & (1LL << 0))
{
continue;
}
// split rem into nr_bits bits
assert(k >= nr_bits);
vector<int> dims;
for (int i = 1; (1LL << i) <= rem; i++)
{
if (rem & (1LL << i))
{
dims.push_back(i);
}
}
int need_extra = k - nr_bits;
for (int i = 0; i < (int)dims.size(); i++)
{
while (dims[i] >= 2 && need_extra > 0)
{
dims.push_back(dims[i] - 1);
dims[i]--;
need_extra--;
}
}
assert(need_extra == 0);
int sumtotal = 0;
for (auto& d : dims)
{
sumtotal += d;
}
vector<int> sol;
for (auto& x : dims)
{
sumtotal -= x;
for (int i = 0; i < x; i++)
{
sol.push_back(sumtotal + i);
}
}
//cout << " : ";
//for (auto& x : sol)
//{
// cout << x << " ";
//}
//cout << "\n";
return sol;
}
return {};
}
