#include "monster.h"
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct Monster {
int index, wins;
bool operator<(const Monster &m) const {
return wins < m.wins;
}
};
std::vector<int> T;
std::vector<Monster> monsters;
/*int findPivot(int from, int to) {
int pivot = T[to - 1];
for (int i = from; i < to - 1; ++i) {
if (Query(i, pivot)) { // i wins
//swap(T[i], T[]);
}
}
}
void findSequence(int from, int to) {
if (from == to + 1) {
return;
}
int pivot = findPivot(from, to);
findSequence(from, pivot);
findSequence(pivot + 1, to);
}*/
std::vector<int> Solve(int N) {
T = std::vector<int>(N);
monsters = std::vector<Monster>(N);
// findSequence(0, N);
for (int i = 0; i < N; ++i) {
monsters[i] = {i, 0};
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < i; ++j) {
if (i == j) {
continue;
}
if (Query(i, j)) { // i wins
++monsters[i].wins;
} else {
++monsters[j].wins;
}
}
}
sort(monsters.begin(), monsters.end());
if (!Query(monsters[0].index, monsters[1].index)) {
swap(monsters[0], monsters[1]);
}
if (Query(monsters[N - 1].index, monsters[N - 2].index)) {
swap(monsters[N - 2], monsters[N - 1]);
}
for (int i = 0; i < N; ++i) {
T[monsters[i].index] = i;
}
return T;
}
