#include "toxic.h"
#include <algorithm>
#include <numeric>
#include <random>
#include <ranges>
void determine_type(int n) {
std::vector<char> ans(n + 1);
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> naturals(n + 1);
std::iota(naturals.begin(), naturals.end(), 0);
std::vector<int> check; // normal, strong
int toxic_loc = 0;
for (int i = 1; i <= n; i += 8) {
auto sample = create_sample(naturals.begin() + i,
naturals.begin() + std::min(n + 1, i + 8));
if (query_sample(sample) == (1 << 8) - 1) {
for (int j = i; j <= std::min(n, i + 7); ++j) {
check.push_back(j);
}
continue;
} else {
std::vector<int> idxs = create_vec(i, std::min(n, i + 7));
while (true) {
int pt = *std::ranges::partition_point(
std::views::iota(0LL, (long long)idxs.size()), [&](int j) {
std::vector<int> sample;
for (int k = 0; k <= j; ++k) {
sample.push_back(idxs[k]);
}
return query_sample(sample) == j + 1;
});
if (pt == idxs.size()) {
break;
}
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) {
check.push_back(idxs[i]);
}
}
}
std::random_device rd;
std::mt19937 rng(rd());
std::shuffle(check.begin(), check.end(), rng);
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);
auto mask = query_sample(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_type(i, ans[i]);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |