| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1353651 | ezzzay | Toxic Gene 2 (NOI24_toxic) | C++20 | 0 ms | 0 KiB |
struct Block {
int l, r;
int rep; // one index inside the block
bool known; // true if already decoded
char type; // 'R' or 'T' when known
};
vector<int> ask(vector<int> reps) {
vector<int> vc;
for (int i = 0; i < (int)reps.size(); i++) {
for (int h = 0; h < (1 << i); h++) vc.pb(reps[i]);
}
return query_machine(vc);
}
void solve(vector<Block> &vec) {
if ((int)vec.size() == 1) return;
vector<Block> nxt;
for (int i = 0; i < (int)vec.size(); i += 8) {
vector<Block> cur;
for (int j = i; j < min(i + 8, (int)vec.size()); j++) cur.pb(vec[j]);
vector<int> reps;
for (auto &b : cur) reps.pb(b.rep);
vector<int> p = ask(reps);
int msk = p.back();
int full = (1 << (int)cur.size()) - 1;
if (msk != full) {
// mixed: child types are known directly
for (int j = 0; j < (int)cur.size(); j++) {
cur[j].known = true;
cur[j].type = (msk & (1 << j)) ? 'T' : 'R';
}
} else {
// uniform, but ambiguous: keep it pending
// do NOT force it to R or T here
}
// merge into parents, but preserve the representative
// the parent is known only if all children in it are known and consistent
nxt.pb({cur[0].l, cur.back().r, cur[0].rep, false, '?'});
}
vec = nxt;
solve(vec);
}