Submission #850672

#	Time	Username	Problem	Language	Result	Execution time	Memory
850672		Forested	Toxic Gene (NOI23_toxic)	C++17	100 / 100	12 ms	708 KiB

toxic

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

• Subtask 1: 100 / 100