#include "grid.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> L, ub;
const int TRIALS = 1;
bool check(int N, int target_stick, int target_level, vector<int> undetermined, vector<int>& determined) {
for (int t = 0; t < TRIALS; t++) {
vector<int> p(1, target_stick);
random_shuffle(undetermined.begin(), undetermined.end());
for (int elm : undetermined) {
if (elm != target_stick) {
p.push_back(elm);
}
}
for (int elm : determined) {
p.push_back(elm);
}
int verdict = PutDisks(p);
int cnt = N - (verdict - N + 1) + 1;
for (int i = 0; i < cnt; i++) {
int guess = i + N - cnt + 1;
ub[p[i]] = min(ub[p[i]], guess);
}
if (verdict < target_level + N - 1) {
return false;
}
}
return true;
}
bool cmp(int u, int v) {
return L[u] < L[v];
}
vector<int> SortDisks(int N) {
L = vector<int>(N, 0);
ub = vector<int>(N, N);
srand(689);
for (int i = N; i >= 1; i--) {
vector<int> determined, undetermined;
for (int j = 0; j < N; j++) {
if (L[j]) {
determined.push_back(j);
} else {
undetermined.push_back(j);
}
}
int only = -1;
for (int elm : undetermined) {
if (ub[elm] >= i) {
if (only == -1) {
only = elm;
} else {
only = -2;
}
}
}
if (only > 0) {
L[only] = i;
continue;
}
sort(determined.begin(), determined.end(), cmp);
random_shuffle(undetermined.begin(), undetermined.end());
for (int elm : undetermined) {
if (ub[elm] < i) {
continue;
}
if (check(N, elm, i, undetermined, determined)) {
L[elm] = i;
break;
}
}
}
return L;
}
