#include "toxic.h"
#include <bits/stdc++.h>
#define OVERRIDE(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define ALL(x) begin(x), end(x)
using namespace std;
using u32 = unsigned int;
using u64 = unsigned long long;
using i32 = signed int;
using i64 = signed long long;
using f64 = double;
using f80 = long double;
template <typename T>
using Vec = vector<T>;
template <typename T>
bool chmin(T &x, const T &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
void determine_type(i32 n) {
static mt19937 mt(998244353);
Vec<i32> idx(n);
iota(ALL(idx), 1);
shuffle(ALL(idx), mt);
auto query = [&](Vec<i32> species) -> i32 {
for (i32 &ele : species) {
ele = idx[ele];
}
return query_sample(species);
};
auto answer = [&](i32 x, char c) -> void {
answer_type(idx[x], c);
};
string ans(n, '-');
Vec<i32> sr, rt;
for (i32 l = 0; l < n; l += 8) {
i32 r = min(l + 8, n);
Vec<i32> species;
REP(i, r - l) {
REP(j, 1 << i) {
species.push_back(l + i);
}
}
i32 ret = query(species);
if (ret == (i32)species.size()) {
REP(i, l, r) {
sr.push_back(i);
}
} else {
Vec<i32> ht;
REP(i, r - l) {
if (ret & (1 << i)) {
ans[l + i] = 'S';
} else {
ht.push_back(l + i);
}
}
// binary search on ht
while (ht.size() > 1) {
Vec<i32> lft(ht.begin(), ht.begin() + ht.size() / 2);
Vec<i32> rgt(ht.begin() + ht.size() / 2, ht.end());
Vec<i32> addi;
while (addi.size() < 8 && sr.size() > 0) {
addi.push_back(sr.back());
sr.pop_back();
}
species = lft;
REP(i, addi.size()) {
REP(j, 1 << i) {
species.push_back(addi[i]);
}
}
ret = query(species);
if (ret == (i32)species.size()) {
for (i32 ele : lft) {
ans[ele] = 'R';
}
for (i32 ele : addi) {
sr.push_back(ele);
}
ht = rgt;
} else {
REP(i, addi.size()) {
if (ret & (1 << i)) {
ans[addi[i]] = 'S';
} else {
ans[addi[i]] = 'R';
}
}
for (i32 ele : rgt) {
rt.push_back(ele);
}
ht = lft;
}
}
ans[ht[0]] = 'T';
}
}
while (rt.size() > 0) {
Vec<i32> ins;
while (ins.size() < 8 && rt.size() > 0) {
ins.push_back(rt.back());
rt.pop_back();
}
{
Vec<i32> addi;
while (addi.size() < 8 && sr.size() > 0) {
addi.push_back(sr.back());
sr.pop_back();
}
Vec<i32> species = ins;
REP(i, addi.size()) {
REP(j, 1 << i) {
species.push_back(addi[i]);
}
}
i32 ret = query(species);
if (ret == (i32)species.size()) {
for (i32 ele : ins) {
ans[ele] = 'R';
}
for (i32 ele : addi) {
sr.push_back(ele);
}
continue;
}
REP(i, addi.size()) {
if (ret & (1 << i)) {
ans[addi[i]] = 'S';
} else {
ans[addi[i]] = 'R';
}
}
}
while (ins.size() > 1) {
Vec<i32> lft(ins.begin(), ins.begin() + ins.size() / 2);
Vec<i32> rgt(ins.begin() + ins.size() / 2, ins.end());
Vec<i32> addi;
while (addi.size() < 8 && sr.size() > 0) {
addi.push_back(sr.back());
sr.pop_back();
}
Vec<i32> species = lft;
REP(i, addi.size()) {
REP(j, 1 << i) {
species.push_back(addi[i]);
}
}
i32 ret = query(species);
if (ret == (i32)species.size()) {
for (i32 ele : lft) {
ans[ele] = 'R';
}
for (i32 ele : addi) {
sr.push_back(ele);
}
ins = rgt;
} else {
REP(i, addi.size()) {
if (ret & (1 << i)) {
ans[addi[i]] = 'S';
} else {
ans[addi[i]] = 'R';
}
}
for (i32 ele : rgt) {
rt.push_back(ele);
}
ins = lft;
}
}
ans[ins[0]] = 'T';
}
while (sr.size() > 0) {
Vec<i32> ins;
while (ins.size() < 8 && sr.size() > 0) {
ins.push_back(sr.back());
sr.pop_back();
}
i32 idx = -1;
REP(i, n) {
if (ans[i] == 'T') {
idx = i;
}
}
assert(idx != -1);
Vec<i32> species;
REP(i, ins.size()) {
REP(j, 1 << i) {
species.push_back(ins[i]);
}
}
species.push_back(idx);
i32 ret = query(species);
REP(i, ins.size()) {
if (ret & (1 << i)) {
ans[ins[i]] = 'S';
} else {
ans[ins[i]] = 'R';
}
}
}
REP(i, n) {
answer(i, ans[i]);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
9 ms |
484 KB |
Output is correct |
| 3 |
Correct |
9 ms |
348 KB |
Output is correct |
| 4 |
Correct |
9 ms |
556 KB |
Output is correct |
| 5 |
Correct |
9 ms |
544 KB |
Output is correct |
| 6 |
Correct |
9 ms |
348 KB |
Output is correct |
| 7 |
Correct |
10 ms |
540 KB |
Output is correct |
| 8 |
Correct |
10 ms |
548 KB |
Output is correct |
| 9 |
Correct |
8 ms |
344 KB |
Output is correct |
| 10 |
Correct |
9 ms |
348 KB |
Output is correct |
| 11 |
Correct |
8 ms |
508 KB |
Output is correct |
| 12 |
Correct |
9 ms |
552 KB |
Output is correct |
| 13 |
Correct |
9 ms |
348 KB |
Output is correct |
| 14 |
Correct |
9 ms |
348 KB |
Output is correct |
| 15 |
Correct |
8 ms |
348 KB |
Output is correct |
| 16 |
Correct |
8 ms |
544 KB |
Output is correct |
| 17 |
Correct |
8 ms |
348 KB |
Output is correct |
| 18 |
Correct |
9 ms |
548 KB |
Output is correct |
| 19 |
Correct |
9 ms |
504 KB |
Output is correct |
| 20 |
Correct |
11 ms |
348 KB |
Output is correct |
| 21 |
Correct |
8 ms |
344 KB |
Output is correct |
| 22 |
Correct |
8 ms |
344 KB |
Output is correct |
| 23 |
Correct |
7 ms |
544 KB |
Output is correct |
| 24 |
Correct |
9 ms |
348 KB |
Output is correct |
| 25 |
Correct |
9 ms |
552 KB |
Output is correct |
| 26 |
Correct |
10 ms |
348 KB |
Output is correct |
| 27 |
Correct |
12 ms |
708 KB |
Output is correct |
| 28 |
Correct |
9 ms |
344 KB |
Output is correct |
| 29 |
Correct |
8 ms |
348 KB |
Output is correct |
| 30 |
Correct |
9 ms |
348 KB |
Output is correct |
| 31 |
Correct |
8 ms |
348 KB |
Output is correct |
| 32 |
Correct |
8 ms |
540 KB |
Output is correct |
| 33 |
Correct |
8 ms |
348 KB |
Output is correct |
| 34 |
Correct |
8 ms |
348 KB |
Output is correct |
| 35 |
Correct |
9 ms |
548 KB |
Output is correct |
| 36 |
Correct |
1 ms |
348 KB |
Output is correct |
