Submission #952078

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
952078	2024-03-23T05:10:19 Z	gaga999	Toxic Gene (NOI23_toxic)	C++17	36.1647 / 100	44 ms	616 KB

toxic

// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define ml(a, b) ((1ll * (a) * (b)) % M)
#define tml(a, b) (a) = ((1ll * (a) * (b)) % M)
#define ad(a, b) ((0ll + (a) + (b)) % M)
#define tad(a, b) (a) = ((0ll + (a) + (b)) % M)
#define mi(a, b) ((0ll + M + (a) - (b)) % M)
#define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M)
#define tmin(a, b) (a) = min((a), (b))
#define tmax(a, b) (a) = max((a), (b))
#define iter(a) (a).begin(), (a).end()
#define riter(a) (a).rbegin(), (a).rend()
#define init(a, b) memset((a), (b), sizeof(a))
#define cpy(a, b) memcpy((a), (b), sizeof(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define size(x) (int)x.size()
#define pb emplace_back
#define mpr make_pair
#define ls(i) ((i) << 1)
#define rs(i) ((i) << 1 | 1)
#define INF 0x3f3f3f3f
#define NIF 0xc0c0c0c0
#define eps 1e-9
#define F first
#define S second
#define AC cin.tie(0)->sync_with_stdio(0)
using namespace std;
typedef long long llt;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
typedef complex<double> cd;
// const int M = 998244353;

// random_device rm;
// mt19937 rg(rm());
// default_random_engine rg(rm());
// uniform_int_distribution<int> rd(INT_MIN, INT_MAX);
// uniform_real_distribution<double> rd(0, M_PI);

void db() { cerr << "\n"; }
template <class T, class... U>
void db(T a, U... b) { cerr << a << " ", db(b...); }

inline char gc()
{
    const static int SZ = 1 << 16;
    static char buf[SZ], *p1, *p2;
    if (p1 == p2 && (p2 = buf + fread(p1 = buf, 1, SZ, stdin), p1 == p2))
        return -1;
    return *p1++;
}
void rd() {}
template <typename T, typename... U>
void rd(T &x, U &...y)
{
    x = 0;
    bool f = 0;
    char c = gc();
    while (!isdigit(c))
        f ^= !(c ^ 45), c = gc();
    while (isdigit(c))
        x = (x << 1) + (x << 3) + (c ^ 48), c = gc();
    f && (x = -x), rd(y...);
}

template <typename T>
void prt(T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        prt(x / 10);
    putchar((x % 10) ^ 48);
}

// int query_sample(vector<int> species){};
// void answer_type(int x, char c){};
int query_sample(vector<int> species);
void answer_type(int x, char c);

int dp[305][35], fr[305][35]; // remain curlen num

void determine_type(int n)
{
    mt19937 rnd(time(NULL));
    for (int nn = 1; nn <= 300; nn++)
    {
        for (int k = 1; k <= 30; k++)
        {
            dp[nn][k] = INF;
            int cg = INF;
            for (int t = 0; 1 << t <= nn; t++)
            {
                int l = 1 << t;
                int res = max(dp[nn - l][k], dp[nn - 1][k - 1] + t) + 1;
                int reg = min(dp[nn - l][k], dp[nn - 1][k - 1] + t) + 1;
                if (res == dp[nn][k] && reg < cg)
                    cg = reg, fr[nn][k] = l;
                if (res < dp[nn][k]) //<=
                    dp[nn][k] = res, fr[nn][k] = l;
            }
        }
    }
    int k = min(30, n), pos = 0;
    vector<int> qs, cr(n), ans(n + 1);
    vector<bool> vd(n + 1);
    iota(iter(cr), 1);
    int bad = 0;
    auto del = [&](const vector<int> &qy) -> void
    {
        for (int i : qy)
        {
            assert(!vd[i]);
            if (!ans[i])
                qs.pb(i);
            else
            {
                vd[i] = 1;
                char c = ans[i] > 0 ? 'R' : 'S';
                // assert(str[i - 1] == c);
                answer_type(i, c);
            }
        }
    };
    auto qry = [&](const vector<int> &qy) -> int
    {
        assert(bad++ < 550);
        int ln = size(qy), res = 0;
        if (ln > 8)
            res = query_sample(qy);
        else
        {
            vector<int> tp;
            for (int i = 0; i < ln; i++)
                for (int j = 1 << i; j > 0; j--)
                    tp.pb(qy[i]);
            shuffle(iter(qs), rnd);
            int kk = min(max(0, 8 - ln), size(qs));
            vector<int> ck(kk);
            for (int i = 0; i < kk; i++)
            {
                assert(!qs.empty());
                ck[i] = qs.back(), qs.pop_back();
                for (int j = 1 << (i + ln); j > 0; j--)
                    tp.pb(ck[i]);
            }
            int re = query_sample(tp);
            for (int i = 0; i < ln; i++)
                if ((re >> i) & 1)
                    res++;
            if (res != ln)
            {
                for (int i = 0; i < ln; i++)
                {
                    // assert(!vd[qy[i]]);
                    if ((re >> i) & 1)
                    {
                        assert(!vd[qy[i]]);
                        // assert(str[qy[i] - 1] == 'S');
                        answer_type(qy[i], 'S'), vd[qy[i]] = 1;
                    }
                    else
                        ans[qy[i]] = 1;
                }
                for (int i = 0; i < kk; i++)
                {
                    // assert(!vd[ck[i]]);
                    char c = ((re >> (i + ln)) & 1) ? 'S' : 'R';
                    // assert(str[ck[i] - 1] == c);
                    assert(!vd[ck[i]]);
                    answer_type(ck[i], c);
                    re &= ~(1 << (i + ln)), vd[ck[i]] = 1;
                }
            }
            else
                for (int i = 0; i < kk; i++)
                    qs.pb(ck[i]);
        }
        if (!res)
            for (int i : qy)
                ans[i] = 1;
        if (res == ln - 1)
            for (int i : qy)
                ans[i] = -1;
        return res;
    };
    auto slv = [&](auto &slv, vector<int> &qy) -> void
    {
        for (int i : qy)
            assert(!vd[i]);
        if (size(qy) == 1)
        {
            // db("okk");
            assert(!vd[qy[0]]);
            // assert(str[qy[0] - 1] == 'T');
            answer_type(qy[0], 'T');
            vd[qy[0]] = 1, pos = qy[0];
            return;
        }
        shuffle(iter(qy), rnd);
        vector<int> tp;
        while (size(qy) > size(tp))
            tp.pb(qy.back()), qy.pop_back();
        int ln = size(tp);
        int res = qry(tp);
        if (res == ln)
        {
            for (int i : tp)
                assert(!vd[i]);
            del(tp), slv(slv, qy);
        }
        else
        {
            for (int i : qy)
                cr.pb(i);
            qy.clear();
            for (int i : tp)
                if (!vd[i])
                    qy.pb(i);
            slv(slv, qy);
        }
    };
    while (!cr.empty())
    {
        int ln = dp[size(cr)][k];
        assert(ln <= size(cr)); //
        shuffle(iter(cr), rnd);
        vector<int> tp(ln);
        for (int i = 0; i < ln; i++)
            tp[i] = cr.back(), cr.pop_back();
        int res = qry(tp);
        if (res == ln)
        {
            // db("delll", ln, size(cr), k);
            for (int i : tp)
                assert(!vd[i]);
            del(tp);
        }
        else
        {
            // db("find t");
            vector<int> qq;
            for (int i : tp)
                if (!vd[i])
                    qq.pb(i);
            slv(slv, qq);
            if (!--k)
                break;
        }
    }
    // assert(str[pos - 1] == 'T');
    qs.clear();
    for (int i = 1; i <= n; i++)
        if (!vd[i])
            qs.pb(i);
    while (!qs.empty())
        qry(vector<int>(1, pos));
    // for (int i = 1; i <= n; i++)
    //     assert(vd[i]);
    assert(pos);
}

// signed main() {}

Subtask #1

36.16470588 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Partially correct	28 ms	604 KB	Partially correct
3	Partially correct	29 ms	600 KB	Partially correct
4	Partially correct	37 ms	616 KB	Partially correct
5	Partially correct	36 ms	604 KB	Partially correct
6	Partially correct	37 ms	600 KB	Partially correct
7	Partially correct	38 ms	604 KB	Partially correct
8	Partially correct	40 ms	604 KB	Partially correct
9	Partially correct	41 ms	604 KB	Partially correct
10	Partially correct	42 ms	604 KB	Partially correct
11	Partially correct	41 ms	604 KB	Partially correct
12	Partially correct	30 ms	600 KB	Partially correct
13	Partially correct	30 ms	604 KB	Partially correct
14	Partially correct	36 ms	600 KB	Partially correct
15	Partially correct	36 ms	604 KB	Partially correct
16	Partially correct	36 ms	604 KB	Partially correct
17	Partially correct	38 ms	604 KB	Partially correct
18	Partially correct	39 ms	604 KB	Partially correct
19	Partially correct	44 ms	604 KB	Partially correct
20	Partially correct	42 ms	604 KB	Partially correct
21	Partially correct	41 ms	604 KB	Partially correct
22	Partially correct	36 ms	600 KB	Partially correct
23	Partially correct	28 ms	604 KB	Partially correct
24	Partially correct	28 ms	604 KB	Partially correct
25	Partially correct	30 ms	600 KB	Partially correct
26	Partially correct	33 ms	600 KB	Partially correct
27	Partially correct	37 ms	600 KB	Partially correct
28	Partially correct	36 ms	616 KB	Partially correct
29	Partially correct	37 ms	616 KB	Partially correct
30	Partially correct	37 ms	604 KB	Partially correct
31	Partially correct	38 ms	604 KB	Partially correct
32	Partially correct	41 ms	600 KB	Partially correct
33	Partially correct	44 ms	600 KB	Partially correct
34	Partially correct	37 ms	600 KB	Partially correct
35	Partially correct	38 ms	604 KB	Partially correct
36	Partially correct	6 ms	348 KB	Partially correct