제출 #1283817

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283817		MisterReaper	Toxic Gene (NOI23_toxic)	C++20	89.20 / 100	8 ms	580 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]) {
        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');

    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 = -1;

    auto identify = [&](auto&& self, std::vector<int> v) -> void {
        debug("NS", v);
        if (v.size() == 1) {
            toxic = v[0];
            send(v[0], 'T');
            return;
        }
        int m = int(v.size());
        std::vector<int> askv;
        std::vector<int> lhs(v.begin(), v.begin() + m / 2);
        std::vector<int> rhs(v.begin() + m / 2, v.end());
        int a = std::min(int(sr.size()), 8 - m / 2);
        for (int i = 0; i < m / 2; ++i) {
            for (int j = 0; j < (1 << i); ++j) {
                askv.emplace_back(v[i]);
            }
        }
        for (int i = 0; i < a; ++i) {
            debug("sr", sr[i]);
            for (int j = 0; j < (1 << (m / 2 + i)); ++j) {
                askv.emplace_back(sr[i]);
            }
        }
        int qval = query_sample(askv);
        debug(qval);
        if (qval == (1 << (m / 2 + a)) - 1) {
            for (int i = 0; i < m / 2; ++i) {
                send(v[i], 'R');
            }
            self(self, rhs);
        } else {
            for (int i = 0; i < a; ++i) {
                if (qval >> (m / 2 + i) & 1) {
                    send(sr[0], 'S');
                } else {
                    send(sr[0], 'R');
                }
                sr.erase(sr.begin());
            }
            for (int i = m / 2; i < m; ++i) {
                tr.emplace_back(v[i]);
            }
            self(self, lhs);
        }
    };

    auto identifytr = [&](auto&& self, std::vector<int> v) -> void {
        debug("TR", v);
        if (v.size() == 1) {
            std::vector<int> askv;
            int a = std::min(int(sr.size()), 8);
            askv.emplace_back(v[0]);
            for (int i = 0; i < a; ++i) {
                for (int j = 0; j < (1 << i); ++j) {
                    askv.emplace_back(sr[i]);
                }
            }
            int qval = query_sample(askv);
            if (qval == 1 << a) {
                send(v[0], 'R');
            } else {
                send(v[0], 'T');
                for (int i = 0; i < a; ++i) {
                    if (qval >> i & 1) {
                        send(sr[0], 'S');
                    } else {
                        send(sr[0], 'R');
                    }
                    sr.erase(sr.begin());
                }
            }
            return;
        }
        int m = int(v.size());
        std::vector<int> askv;
        std::vector<int> lhs(v.begin(), v.begin() + m / 2);
        std::vector<int> rhs(v.begin() + m / 2, v.end());
        int a = std::min(int(sr.size()), 8 - m / 2);
        for (int i = 0; i < m / 2; ++i) {
            for (int j = 0; j < (1 << i); ++j) {
                askv.emplace_back(v[i]);
            }
        }
        for (int i = 0; i < a; ++i) {
            debug(sr[i]);
            for (int j = 0; j < (1 << (m / 2 + i)); ++j) {
                askv.emplace_back(sr[i]);
            }
        }
        int qval = query_sample(askv);
        debug(qval);
        if (qval == (1 << (m / 2 + a)) - 1) {
            for (int i = 0; i < m / 2; ++i) {
                send(v[i], 'R');
            }
            self(self, rhs);
        } else {
            for (int i = 0; i < a; ++i) {
                if (qval >> (m / 2 + i) & 1) {
                    send(sr[0], 'S');
                } else {
                    send(sr[0], 'R');
                }
                sr.erase(sr.begin());
            }
            for (int i = m / 2; i < m; ++i) {
                tr.emplace_back(v[i]);
            }
            self(self, lhs);
        }
    };

    while (!notsure.empty()) {
        int m = std::min(8, int(notsure.size()));
        std::vector<int> get(m);
        for (int i = 0; i < m; ++i) {
            get[i] = notsure.back();
            notsure.pop_back();
        }

        debug(get);
        
        std::vector<int> v;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < (1 << i); ++j) {
                v.emplace_back(get[i]);
            }
        }
        int qval = query_sample(v);
        debug(qval);
        if (qval == (1 << m) - 1) {
            for (int i = 0; i < m; ++i) {
                sr.emplace_back(get[i]);
            }
        } else {
            std::vector<int> oth;
            for (int i = 0; i < m; ++i) {
                if (qval >> i & 1) {
                    send(get[i], 'S');
                } else {
                    oth.emplace_back(get[i]);
                }
            }
            identify(identify, oth);
        }
    }

    assert(toxic != -1);

    while (!tr.empty()) {
        int m = std::min(8, int(tr.size()));
        std::vector<int> get(m);
        for (int i = 0; i < m; ++i) {
            get[i] = tr.back();
            tr.pop_back();
        }
        if (query_sample(get) == 0) {
            identifytr(identifytr, get);
        } else {
            for (int i = 0; i < m; ++i) {
                send(get[i], 'R');
            }
        }
    }

    while (!sr.empty()) {
        int m = std::min(8, int(sr.size()));
        std::vector<int> get(m);
        for (int i = 0; i < m; ++i) {
            get[i] = sr.back();
            sr.pop_back();
        }
        std::vector<int> v;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < (1 << i); ++j) {
                v.emplace_back(get[i]);
            }
        }
        v.emplace_back(toxic);
        int qval = query_sample(v);
        for (int i = 0; i < m; ++i) {
            if (qval >> i & 1) {
                send(get[i], 'S');
            } else {
                send(get[i], 'R');
            }
        }
    }
}

• Subtask 1: 89.2 / 100