#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
struct permutation {
array<uint8_t, 6> p;
permutation(array<uint8_t, 6> array) : p(array) {}
array<uint8_t, 6> decompress() { return p; }
//uint16_t order;
//permutation(array<uint8_t, 6> array) : order(0) {
// for (int i = 0; i < 5; ++i)
// order |= (uint16_t)((int)array[i] << (3*i));
//}
//array<uint8_t, 6> decompress() {
// array<uint8_t, 6> ans;
// uint8_t last=0^1^2^3^4^5;
// for (int i = 0; i < 5; ++i) {
// uint8_t x = (order >> (3*i))&0x7;
// ans[i] = x;
// last ^= x;
// }
// ans[5] = last;
// return ans;
//}
};
int lightest(array<uint8_t, 6> p, int a, int b, int c) {
if (p[a] < p[b] && p[a] < p[c]) return 0;
if (p[b] < p[a] && p[b] < p[c]) return 1;
if (p[c] < p[a] && p[c] < p[b]) return 2;
assert(false);
}
int heaviest(array<uint8_t, 6> p, int a, int b, int c) {
if (p[a] > p[b] && p[a] > p[c]) return 0;
if (p[b] > p[a] && p[b] > p[c]) return 1;
if (p[c] > p[a] && p[c] > p[b]) return 2;
assert(false);
}
int median(array<uint8_t, 6> p, int a, int b, int c) {
if ((p[a] > p[b] && p[a] < p[c]) ||
(p[a] < p[b] && p[a] > p[c])) return 0;
if ((p[b] > p[a] && p[b] < p[c]) ||
(p[b] < p[a] && p[b] > p[c])) return 1;
if ((p[c] > p[a] && p[c] < p[b]) ||
(p[c] < p[a] && p[c] > p[b])) return 2;
assert(false);
}
int next_lightest(array<uint8_t, 6> p, int a, int b, int c, int d) {
int ans = -1;
if (p[a] > p[d]) ans = a;
if (p[b] > p[d]) if (ans == -1 || p[b] < p[ans]) ans = b;
if (p[c] > p[d]) if (ans == -1 || p[c] < p[ans]) ans = c;
if (ans == -1) return lightest(p, a, b, c);
else return (ans==a ? 0 : (ans==b ? 1 : 2));
}
struct decision {
vector<permutation> state;
int question;
int a, b, c, d;
array<unique_ptr<decision>, 3> child;
static unique_ptr<decision> solved(vector<permutation> s) {
return unique_ptr<decision>(new decision{s, -1, 0,0,0,0, {nullptr, nullptr, nullptr}});
}
void interact() {
if (state.size() == 0) assert(false);
if (state.size() == 1) {
auto p = state[0].decompress();
vector<int> inv(6);
for (int i = 0; i < 6; ++i)
inv[p[i]] = i+1;
answer(inv.data());
return;
}
int ans=0;
switch (question) {
case 0: ans = getLightest(a+1, b+1, c+1); break;
case 1: ans = getHeaviest(a+1, b+1, c+1); break;
case 2: ans = getMedian(a+1, b+1, c+1); break;
case 3: ans = getNextLightest(a+1, b+1, c+1, d+1); break;
default: assert(false);
}
if (ans == a+1) child[0]->interact();
else if (ans == b+1) child[1]->interact();
else if (ans == c+1) child[2]->interact();
else assert(false);
}
};
void print(unique_ptr<decision> const& d, int depth=0) {
string indent = string(2*depth, ' ');
cout << indent << "// " << d->state.size() << '\n';
cout << indent << " ";
if (d->state.size() == 0) {
cout << "assert(false);\n";
return;
}
if (d->state.size() == 1) {
auto p = d->state[0].decompress();
cout << "answer(std::array<int, 6>{";
const char *sep="";
for (auto x : p) {
cout << sep << (int)x+1;
sep = ", ";
}
cout << "}.data());\n";
return;
}
array<const char*, 4> function_name{
"getLightest",
"getHeaviest",
"getMedian",
"getNextLightest",
};
cout << "switch (" << function_name[d->question] << '(' << (int)d->a+1 << ", " << (int)d->b+1 << ", " << (int)d->c+1;
if (d->d != -1)
cout << ", " << (int)d->d+1;
cout << ")) {\n";
for (int i = 0; i < 3; ++i) {
cout << indent << " case "<<(i==0?d->a+1:(i==1?d->b+1:d->c+1))<<":\n ";
print(d->child[i], depth+1);
cout << indent << " break;\n";
}
cout << indent << " default: assert(false);\n";
cout << indent << " }\n";
}
int pow3(int e) {
if (e <= 0) return 1;
return 3*pow3(e-1);
}
unique_ptr<decision> solve(vector<permutation> state, int max_depth);
template <typename F>
unique_ptr<decision> subsolve(int q, F&& f, vector<permutation> const& state, int max_depth) {
int max_child_size = pow3(max_depth);
for (int a = 0; a < 6; ++a) {
for (int b = a+1; b < 6; ++b) {
for (int c = b+1; c < 6; ++c) {
array<vector<permutation>, 3> child;
array<unique_ptr<decision>, 3> ans;
for (auto s : state) {
auto p = s.decompress();
int r = f(p, a, b, c);
assert(0 <= r && r < 3);
child[r].push_back(s);
if ((int)child[r].size() > max_child_size)
goto next;
}
// cout << "S"<<q << " " << max_depth << " " << max_child_size << ' ' << a << ' ' << b << ' ' << c << " | ";
// for (int i = 0; i < 3; ++i) {
// cout << child[i].size() << ' ';
// }
// cout << '\n';
for (int i = 0; i < 3; ++i) {
ans[i] = solve(child[i], max_depth);
if (!ans[i]) goto next;
}
return unique_ptr<decision>(new decision{state, q, a, b, c, -1, move(ans)});
next:;
}
}
}
return nullptr;
}
unique_ptr<decision> subsolve4(int q, vector<permutation> const& state, int max_depth) {
int max_child_size = pow3(max_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 < 6; ++d) {
if (d==a || d==b || d==c) continue;
array<vector<permutation>, 3> child;
array<unique_ptr<decision>, 3> ans{};
for (auto s : state) {
auto p = s.decompress();
int x = next_lightest(p, a, b, c, d);
child[x].push_back(s);
if ((int)child[x].size() > max_child_size)
goto next;
}
for (int i = 0; i < 3; ++i) {
ans[i] = solve(child[i], max_depth);
if (!ans[i]) goto next;
}
// cout << "S"<<4 << " " << max_depth << " " << max_child_size << ' ' << a << ' ' << b << ' ' << c << " | ";
// for (int i = 0; i < 3; ++i) {
// cout << child[i].size() << ' ';
// }
// cout << '\n';
return unique_ptr<decision>(new decision{state, q, a, b, c, d, move(ans)});
next:;
}
}
}
}
return nullptr;
}
unique_ptr<decision> solve(vector<permutation> state, int max_depth) {
if (state.size() <= 1)
return decision::solved(state);
if ((int)state.size() > pow3(max_depth)) return nullptr;
assert(max_depth >= 1);
if (auto ans = subsolve(0, lightest, state, max_depth-1)) return ans;
if (auto ans = subsolve(1, heaviest, state, max_depth-1)) return ans;
if (auto ans = subsolve(2, median, state, max_depth-1)) return ans;
if (auto ans = subsolve4(3, state, max_depth-1)) return ans;
return nullptr;
}
unique_ptr<decision> decision_tree;
void init(int) {
vector<permutation> state;
array<uint8_t, 6> p = {0,1,2,3,4,5};
do {
state.push_back(permutation(p));
assert(p==permutation(p).decompress());
} while (next_permutation(p.begin(), p.end()));
decision_tree = solve(state, 7);
if (!decision_tree) { cout << "no solution found\n"; }
assert(decision_tree);
//print(decision_tree);
}
void orderCoins() {
decision_tree->interact();
}
