#include "toxic.h"
#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
namespace {
std::vector<int> ans;
void send(int p, char c) {
if (ans[p]) {
debug("bad", p, c);
return;
}
ans[p] = true;
debug(p, c);
answer_type(p, c);
}
std::random_device rd;
std::mt19937 rng(23);
};
void determine_type(int n){
// std::vector<int> v;
// v.push_back(1);
// int qvalue = query_sample(v);
// answer_type(1,'T');
debug("NEW TC: ", n);
ans.assign(n + 1, 0);
std::vector<int> ord(n);
std::iota(ord.begin(), ord.end(), 1);
std::shuffle(ord.begin(), ord.end(), rng);
std::vector<int> sr, tr, notsure;
for (int i = 0; i < n; ++i) {
notsure.emplace_back(ord[i]);
}
int toxic = 0;
auto checknotsure = [&](std::vector<int> v) -> bool {
if (v.size() == 0) {
return false;
}
int m = int(v.size());
std::vector<int> askv;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < (1 << i); ++j) {
askv.emplace_back(v[i]);
}
}
int k = std::min(int(sr.size()), 8 - m);
for (int i = 0; i < k; ++i) {
for (int j = 0; j < (1 << (m + i)); ++j) {
askv.emplace_back(sr[i]);
}
}
int qval = query_sample(askv);
// debug(qval);
if (qval == (1 << (m + k)) - 1) {
return false;
} else {
for (int i = 0; i < m; ++i) {
if (qval >> i & 1) {
send(v[i], 'S');
}
}
for (int i = 0; i < k; ++i) {
if (qval >> (m + i) & 1) {
send(sr[0], 'S');
} else {
send(sr[0], 'R');
}
sr.erase(sr.begin());
}
return true;
}
};
auto checktr = [&](std::vector<int> v) -> bool {
if (int(v.size()) == 0) {
return false;
}
int m = int(v.size());
std::vector<int> askv;
for (int i = 0; i < m; ++i) {
askv.emplace_back(v[i]);
}
int k = std::min(int(sr.size()), 8);
for (int i = 0; i < k; ++i) {
for (int j = 0; j < (1 << i); ++j) {
askv.emplace_back(sr[i]);
}
}
int qval = query_sample(askv);
if (qval == (1 << k) - 1 + m) {
return false;
} else {
for (int i = 0; i < k; ++i) {
if (qval >> i & 1) {
send(sr[0], 'S');
} else {
send(sr[0], 'R');
}
sr.erase(sr.begin());
}
return true;
}
};
auto identify = [&](auto&& self, std::vector<int> v) -> void {
if (int(v.size()) == 1) {
toxic = v[0];
send(v[0], 'T');
return;
}
int m = int(v.size());
int hlf = m / 2;
std::vector<int> lhs(v.begin(), v.begin() + hlf);
std::vector<int> rhs(v.begin() + hlf, v.end());
// debug(lhs, rhs);
if (checktr(lhs)) {
for (auto i : rhs) {
tr.emplace_back(i);
}
self(self, lhs);
} else {
for (auto i : lhs) {
send(i, 'R');
}
self(self, rhs);
}
};
while (!notsure.empty()) {
int m = std::min(int(notsure.size()), 8);
std::vector<int> v;
for (int i = 0; i < m; ++i) {
v.emplace_back(notsure.back());
notsure.pop_back();
}
// debug(v);
if (checknotsure(v)) {
std::vector<int> nv;
for (int i = 0; i < m; ++i) {
if (ans[v[i]] == false) {
nv.emplace_back(v[i]);
}
}
// debug(nv);
identify(identify, nv);
} else {
for (auto i : v) {
sr.emplace_back(i);
}
}
}
debug("fin", std::accumulate(ans.begin(), ans.end(), 0), tr.size(), sr.size(), notsure.size());
while (!tr.empty()) {
int m = std::min(int(tr.size()), 8);
std::vector<int> v;
for (int i = 0; i < m; ++i) {
v.emplace_back(tr.back());
tr.pop_back();
}
if (checktr(v)) {
identify(identify, v);
} else {
for (auto i : v) {
send(i, 'R');
}
}
}
assert(toxic != 0);
while (!sr.empty()) {
checktr({toxic});
}
}
