Submission #952122

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
952122	2024-03-23T06:18:20 Z	gaga999	Toxic Gene (NOI23_toxic)	C++17	85.15 / 100	178 ms	856 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);

double dp[305][35];
int 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;
            for (int t = 0; 1 << t <= nn; t++)
            {
                int l = 1 << t;
                double rt = dp[nn - 1][k - 1] + t + 1;
                double rn = dp[nn - l][k] + 1;
                double res;
                // if (rn > rt)
                //     res = rn;
                // else
                // {
                if (nn - k < l)
                    res = rt;
                else
                {
                    double p = pow((nn - k - l / 2) / double(nn), l);
                    res = rn * p + rt * (1 - p);
                }
                //}
                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++ < 301);
        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(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 = min(size(cr), 10); // fr[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);
            // assert(bad - pbad <= log2(ln));
            slv(slv, qq);
            if (!--k)
                break;
        }
    }
    // assert(str[pos - 1] == 'T');
    for (int i : cr)
        qs.pb(i);
    bad = 0;
    while (!qs.empty())
        qry(vector<int>(1, pos));
    // for (int i = 1; i <= n; i++)
    //     assert(vd[i]);
    assert(pos);
}

// signed main() {}

Subtask #1

85.15 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	604 KB	Output is correct
2	Partially correct	169 ms	604 KB	Partially correct
3	Partially correct	170 ms	604 KB	Partially correct
4	Correct	175 ms	612 KB	Output is correct
5	Partially correct	175 ms	856 KB	Partially correct
6	Partially correct	169 ms	604 KB	Partially correct
7	Partially correct	168 ms	604 KB	Partially correct
8	Partially correct	177 ms	612 KB	Partially correct
9	Partially correct	169 ms	608 KB	Partially correct
10	Correct	170 ms	604 KB	Output is correct
11	Correct	172 ms	612 KB	Output is correct
12	Partially correct	176 ms	604 KB	Partially correct
13	Correct	169 ms	600 KB	Output is correct
14	Partially correct	170 ms	612 KB	Partially correct
15	Partially correct	169 ms	608 KB	Partially correct
16	Partially correct	168 ms	604 KB	Partially correct
17	Partially correct	168 ms	600 KB	Partially correct
18	Partially correct	172 ms	612 KB	Partially correct
19	Partially correct	170 ms	604 KB	Partially correct
20	Correct	171 ms	600 KB	Output is correct
21	Correct	178 ms	624 KB	Output is correct
22	Correct	170 ms	600 KB	Output is correct
23	Correct	168 ms	604 KB	Output is correct
24	Partially correct	171 ms	604 KB	Partially correct
25	Partially correct	168 ms	604 KB	Partially correct
26	Correct	171 ms	600 KB	Output is correct
27	Partially correct	170 ms	600 KB	Partially correct
28	Correct	170 ms	604 KB	Output is correct
29	Partially correct	168 ms	600 KB	Partially correct
30	Partially correct	168 ms	604 KB	Partially correct
31	Partially correct	172 ms	604 KB	Partially correct
32	Partially correct	174 ms	612 KB	Partially correct
33	Correct	169 ms	604 KB	Output is correct
34	Partially correct	175 ms	608 KB	Partially correct
35	Partially correct	168 ms	604 KB	Partially correct
36	Partially correct	21 ms	348 KB	Partially correct