#include "toxic.h"
#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <numeric>
#include <random>
#include <ranges>
int BinarySearchMin(int s, int e, const std::function<bool(int)> &f) {
while (s < e) {
int m = s + (e - s) / 2;
if (f(m)) {
e = m;
} else {
s = m + 1;
}
}
return s;
}
void determine_type(int n) {
std::vector<char> ans(n + 1);
std::vector<int> p(n);
std::iota(p.begin(), p.end(), 0);
std::random_device rd;
std::mt19937 gen(rd());
std::shuffle(p.begin(), p.end(), gen);
// with randomized index locs, new funcs
auto query = [&](std::vector<int> sample) {
// std::cout << "sample size: " << sample.size() << '\n';
for (auto &i : sample) {
i = p[i - 1] + 1;
}
return query_sample(sample);
};
auto answer = [&](int i, char x) { answer_type(p[i - 1] + 1, x); };
auto create_vec = [](int s, int e) {
std::vector<int> ans;
for (int i = s; i <= e; ++i) {
ans.push_back(i);
}
return ans;
};
auto create_sample = [&](std::vector<int>::iterator begin,
std::vector<int>::iterator end) {
std::vector<int> sample;
for (int bt = 0; bt < 8 and begin != end; ++bt, ++begin) {
for (int j = 0; j < (1 << bt); ++j) {
sample.push_back(*begin);
}
}
return sample;
};
std::vector<int> check; // normal, strong
std::vector<int> naturals(n + 1);
std::iota(naturals.begin(), naturals.end(), 0);
int toxic_loc = 0;
std::vector<int> future_queries(n + 1);
std::vector<std::vector<int>> future_idxs(n + 1);
std::vector<bool> modified(
n + 1); // did we potentially remove a toxic from future idxs[i]?
for (int i = 1; i <= n; i += 8) {
auto sample = create_sample(naturals.begin() + i,
naturals.begin() + std::min(n + 1, i + 8));
int mask = query(sample);
if (mask == sample.size()) {
for (int j = i; j <= std::min(n, i + 7); ++j) {
check.push_back(j);
}
} else {
std::vector<int> idxs;
for (int j = i, bt = 0; j <= std::min(n, i + 7); ++j, ++bt) {
if (mask & (1 << bt)) {
ans[j] = 'S';
} else {
idxs.push_back(j);
}
}
future_idxs[i] = idxs;
}
future_queries[i] = mask;
}
for (int i = 1; i <= n; i += 8) {
auto sample = create_sample(naturals.begin() + i,
naturals.begin() + std::min(n + 1, i + 8));
int mask = future_queries[i];
if (mask != sample.size()) {
std::vector<int> idxs = future_idxs[i];
if (idxs.empty()) {
continue;
}
// if we're modified and there's something ahead that's not modified, take
// it
if (modified[i]) {
for (int j = i + 1; j <= n; ++j) {
if (!future_idxs[j].empty() and !modified[j]) {
std::swap(idxs, future_idxs[j]);
modified[i] = false;
modified[j] = true;
break;
}
}
}
// move ahead indices to behind free spots if you can
// till the size is not a power of 2
while (idxs.size() & (idxs.size() - 1)) {
while (!future_idxs.empty() and future_idxs.back().empty()) {
future_idxs.pop_back();
}
if (future_idxs.empty() or future_idxs.size() - 1 == i) {
break;
}
idxs.push_back(future_idxs.back().back());
future_idxs.back().pop_back();
modified[future_idxs.size() - 1] = true;
}
while (!modified[i] or query(idxs) != idxs.size()) {
modified[i] = true; // free first query
int pt = BinarySearchMin(0, idxs.size() - 1, [&](int j) {
std::vector<int> sample; // only toxic and normal
for (int k = 0; k <= j; ++k) {
sample.push_back(idxs[k]);
}
// add some things we can basically do a free check with
int k = 0; // number of things we added
std::vector<int> things_rem;
for (; k < 8 and !check.empty(); ++k) {
for (int bt = 0; bt < (1 << k); ++bt) {
sample.push_back(check.back());
}
things_rem.push_back(check.back());
check.pop_back();
}
int mask = query(sample);
if (mask == sample.size()) {
for (auto &i : things_rem) {
check.push_back(i);
}
return false;
}
for (int bt = 0; bt < k; ++bt) {
if (mask & (1 << bt)) {
ans[things_rem[bt]] = 'S';
} else {
ans[things_rem[bt]] = 'R';
}
}
return true;
});
ans[idxs[pt]] = 'T';
toxic_loc = idxs[pt];
idxs.erase(idxs.begin() + pt);
std::sort(idxs.begin(), idxs.end());
}
for (int i = 0; i < idxs.size(); ++i) {
ans[idxs[i]] = 'R';
}
}
}
for (int i = 0; i < check.size(); i += 8) {
auto sample = create_sample(
check.begin() + i, check.begin() + std::min(int(check.size()), i + 8));
sample.push_back(toxic_loc); // normal and strong + one toxic
auto mask = query(sample);
for (int bt = 0; bt < 8 and i + bt < check.size(); ++bt) {
if (mask & (1 << bt)) {
ans[check[i + bt]] = 'S';
} else {
ans[check[i + bt]] = 'R';
}
}
}
for (int i = 1; i <= n; ++i) {
answer(i, ans[i]);
}
}
