scales.cpp

#include "scales.h"
#include <map>
#include <set>
#include <cassert>
#include <algorithm>

using namespace std;

inline int _getMedian(int arr[6], int a, int b, int c)
{
	return arr[a] < arr[b] ? (arr[b] < arr[c] ? b : (arr[a] < arr[c] ? c : a)) : (arr[a] < arr[c] ? a : (arr[b] < arr[c] ? c : b));
}

inline int _getHeaviest(int arr[6], int a, int b, int c)
{
	return arr[a] < arr[b] ? (arr[b] < arr[c] ? c : b) : (arr[a] < arr[c] ? c : a);
}

inline int _getLightest(int arr[6], int a, int b, int c)
{
	return arr[a] < arr[b] ? (arr[a] < arr[c] ? a : c) : (arr[b] < arr[c] ? b : c);
}

inline int _getNextLightest(int arr[6], int a, int b, int c, int d)
{
	return arr[a] < arr[d] ? (arr[b] < arr[d] ? (arr[c] < arr[d] ? _getLightest(arr, a, b, c) : c) : (arr[c] < arr[d] ? b : (arr[b] < arr[c] ? b : c)))
							: (arr[b] < arr[d] ? (arr[c] < arr[d] ? a : (arr[a] < arr[c] ? a : c)) : (arr[c] < arr[d] ? (arr[a] < arr[b] ? a : b) : _getLightest(arr, a, b, c)));
}

int _query(int arr[6], int a, int b, int c, int d)
{
	switch (d)
	{
	case 6:
		return _getMedian(arr, a, b, c);
	case 7:
		return _getLightest(arr, a, b, c);
	case 8:
		return _getHeaviest(arr, a, b, c);
	default:
		return _getNextLightest(arr, a, b, c, d);
	}
}

int query(int a, int b, int c, int d)
{
	++a, ++b, ++c;
	switch (d)
	{
	case 6:
		return getMedian(a, b, c);
	case 7:
		return getLightest(a, b, c);
	case 8:
		return getHeaviest(a, b, c);
	default:
		return getNextLightest(a, b, c, d + 1);
	}
}

int arrs[720][6];
int res[720][6][6][6][9];
map<set<int>, tuple<int, int, int, int>> mem;

const tuple<int, int, int, int> FAIL {-1, -1, -1, -1};

int depth;

int pow3[] = {1, 3, 9, 27, 81, 243, 729};

bool calc(const set<int>& s)
{
	if (s.size() <= 1)
		return true;
	if (mem.count(s))
		return mem[s] != FAIL;
	
	++depth;
	
	for (int a = 0; a < 6; ++a) for (int b = a + 1; b < 6; ++b) for (int c = b + 1; c < 6; ++c) for (int d = 0; d < 9; ++d) if (a != d && b != d && c != d)
	{
		set<int> s2[3];
		
		for (const int& val: s)
			s2[res[val][a][b][c][d]].insert(val);
		
		if (max(s2[0].size(), max(s2[1].size(), s2[2].size())) <= pow3[6 - depth]
			&& all_of(s2, s2 + 3, calc))
		{
			return mem[s] = make_tuple(a, b, c, d), --depth, true;
		}
	}
	
	return mem[s] = FAIL, --depth, false;
}

void init(int T)
{
	int arr[6] = {0, 1, 2, 3, 4, 5};
	for (int i = 0; i < 720; ++i, next_permutation(arr, arr + 6))
	{
		for (int j = 0; j < 6; ++j)
			arrs[i][arr[j]] = j + 1;
		for (int a = 0; a < 6; ++a) for (int b = a + 1; b < 6; ++b) for (int c = b + 1; c < 6; ++c) for (int d = 0; d < 9; ++d) if (a != d && b != d && c != d)
		{
			int x = _query(arr, a, b, c, d);
			res[i][a][b][c][d] = (x == b) + 2 * (x == c);
		}
	}
}

void orderCoins()
{
	set<int> s;
	for (int i = 0; i < 720; ++i)
		s.insert(i);
	
	int a, b, c, d, x;
	while (s.size() != 1)
	{
		assert(calc(s));
		tie(a, b, c, d) = mem[s];
		
		x = query(a, b, c, d) - 1;
		x = (x == b) + 2 * (x == c);
		
		set<int> s2;
		
		for (const int& val: s) if (res[val][a][b][c][d] == x)
			s2.insert(val);
		
		swap(s, s2);
	}
	
	answer(arrs[*s.begin()]);
}