#include "grid.h"
#include <random>
#include <algorithm>
#include <map>
using namespace std;
int n;
vector<int> ans;
vector<int> idx;
map<vector<int>, int> logs;
vector<vector<bool>> vis;
int count_candi(int x){
int cnt = 0;
for(int i=0;i<n;i++){
if (vis[x][i])cnt++;
}
return cnt;
}
int get_max_disk(int x) {
vector<int> v;
std::random_device rd;
std::mt19937 g(rd());
for(int i=0;i<n;i++){
if (!ans[i]){
v.push_back(i);
}
}
int p = x;
int cnt = 0;
while(p){
cnt++;
p /= 2;
}
for(int i=0;i<cnt;i++){
if (count_candi(x) < x/20)break;
shuffle(v.begin(), v.end(), g);
vector<int> t = v;
for(int j=x+1; j<=n; j++){
t.push_back(idx[j]);
}
int r = logs[t];
if (!r){
r = PutDisks(t);
logs[t] = r;
}
r -= (n-x);
r -= x - 1;
for(int q = x-r; q >= 1; q--){
for(int j=0;j<q;j++){
vis[q+r][v[j]] = false;
}
}
}
for(int i=0;i<n;i++){
if (vis[x][i]){
//printf("#");
vector<int> v;
v.push_back(i);
for(int j=0;j<n;j++){
if (!ans[j] && j != i){
v.push_back(j);
}
}
for(int j=x+1;j<=n;j++){
v.push_back(idx[j]);
}
int r = logs[v];
if(!r){
r = PutDisks(v);
logs[v] = r;
}
if (r - (n-x) == 2*x-1) {
puts("");
return i;
}
}
}
return -1;
}
std::vector<int> SortDisks(int N) {
n = N;
ans.resize(n);
idx.resize(n+1);
vis.resize(n+1);
for(int i=1;i<=n;i++){
vis[i].resize(n, true);
}
for(int i=n;i>=1;i--){
int x = get_max_disk(i);
ans[x] = i;
idx[i] = x;
for(int j=1;j<i;j++){
vis[j][x] = false;
}
}
return ans;
}
