Submission #1283943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283943		MisterReaper	Toxic Gene (NOI23_toxic)	C++20	100 / 100	9 ms	504 KiB

toxic

#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});
    }
}

• Subtask 1: 100 / 100