#include "scales.h"
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = x; i < y; ++i)
#define pb push_back
vector<vector<int>> UNI;
vector<vector<int>> Q;
void init(int T) {
// cout << "starting preprocessing\n";
vector<int> tmp = {1, 2, 3, 4, 5, 6};
UNI.pb(tmp);
while(next_permutation(tmp.begin(), tmp.end())){
UNI.pb(tmp);
}
FOR(i, 1, 7){
FOR(j, i + 1, 7){
FOR(k, j + 1, 7){
FOR(ii, 0, 3){
Q.pb({i, j, k, ii});
Q.pb({i, k, j, ii});
Q.pb({j, i, k, ii});
Q.pb({j, k, i, ii});
Q.pb({k, j, i, ii});
Q.pb({k, i, j, ii});
}
}
}
}
set<vector<int>> s;
FOR(i, 0, UNI.size()){
vector<int> TMP = {UNI[i][0], UNI[i][1], UNI[i][2], UNI[i][3], 0};
if (s.count(TMP) == 0){
s.insert(TMP);
Q.pb(TMP);
}
}
// cout << "preprocessed\n";
return;
}
int qans(vector<int>& q, vector<int>& pos){
if (q.size() == 4){
if (q.back() == 0){
//smallest
FOR(i, 0, pos.size()){
FOR(j, 0, 3){
if (pos[i] == q[j]){
return q[j];
}
}
}
}
else if (q.back() == 2){
//largest
FOR(i, 0, pos.size()){
FOR(j, 0, 3){
if (pos[5 - i] == q[j]){
return q[j];
}
}
}
}
else{
//median
bool flag = false;
FOR(i, 0, pos.size()){
FOR(j, 0, 3){
if (pos[i] == q[j]){
if (flag){
return q[j];
}
else{
flag = true;
}
}
}
}
}
}
//4 coins on scale
int small = -1;
bool flag = false;
FOR(i, 0, pos.size()){
FOR(j, 0, 3){
if (pos[i] == q[j]){
if (small == -1){
small = q[j];
}
if (flag){
return q[j];
}
}
}
if (pos[i] == q[4]){
flag = true;
}
}
return small;
}
pair<int, long double> value(vector<int>& q, vector<vector<int>>& uni){
vector<int> dist(6);
FOR(i, 0, uni.size()){
dist[qans(q, uni[i]) - 1]++;
}
int ans = 0;
long double ans2 = 0;
FOR(i, 0, dist.size()){
ans2 += dist[i]*dist[i];
if (dist[i] > ans){
ans = dist[i];
}
}
ans2 = sqrt(ans2/3);
return {ans, ans2};
}
void orderCoins() {
/* ... */
int C = 0;
vector<vector<int>> uni = UNI;
while(uni.size() > 1){
// cout << C << "\n";
C++;
vector<pair<int, long double>> qv(Q.size());
FOR(i, 0, Q.size()){
qv[i] = value(Q[i], uni);
}
// cout << "values calculated\n";
int ind = 0;
pair<int, long double> ans = qv[0];
FOR(i, 0, qv.size()){
if (qv[i].first < ans.first){
ans = qv[i];
ind = i;
}
if (qv[i].first == ans.first){
if (qv[i].second < ans.second){
ans = qv[i];
ind = i;
}
}
}
// cout << ans.first << " " << ans.second << "\n";
// FOR(i, 0, Q[ind].size()){
// cout << Q[ind][i] << " ";
// }
// cout << "\n";
int A;
if (Q[ind].size() == 4){
if (Q[ind].back() == 0){
A = getLightest(Q[ind][0], Q[ind][1], Q[ind][2]);
}
else if (Q[ind].back() == 2){
A = getHeaviest(Q[ind][0], Q[ind][1], Q[ind][2]);
}
else{
A = getMedian(Q[ind][0], Q[ind][1], Q[ind][2]);
}
}
else{
A = getNextLightest(Q[ind][0], Q[ind][1], Q[ind][2], Q[ind][3]);
}
//cout << "A = " << A << "\n";
vector<vector<int>> Nuni;
FOR(i, 0, uni.size()){
if (qans(Q[ind], uni[i]) == A){
Nuni.pb(uni[i]);
}
}
swap(Nuni, uni);
}
//cout << "Done\n";
int W[] = {uni[0][0], uni[0][1], uni[0][2], uni[0][3], uni[0][4], uni[0][5]};
//cout << "Answer is: ";
//FOR(i, 0, 6){
// cout << W[i] << " ";
//}
//cout << "\n";
answer(W);
return;
}
