Submission #952115

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
952115	2024-03-23T06:12:40 Z	gaga999	Toxic Gene (NOI23_toxic)	C++17	42.1176 / 100	209 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 = 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");
            int pbad = bad;
            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() {}

Compilation message

toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:257:17: warning: unused variable 'pbad' [-Wunused-variable]
  257 |             int pbad = bad;
      |                 ^~~~

Subtask #1

42.11764706 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	344 KB	Output is correct
2	Partially correct	201 ms	616 KB	Partially correct
3	Partially correct	204 ms	616 KB	Partially correct
4	Partially correct	206 ms	852 KB	Partially correct
5	Partially correct	178 ms	604 KB	Partially correct
6	Partially correct	180 ms	604 KB	Partially correct
7	Partially correct	178 ms	604 KB	Partially correct
8	Partially correct	178 ms	604 KB	Partially correct
9	Partially correct	181 ms	608 KB	Partially correct
10	Correct	179 ms	612 KB	Output is correct
11	Correct	179 ms	600 KB	Output is correct
12	Partially correct	199 ms	616 KB	Partially correct
13	Partially correct	206 ms	604 KB	Partially correct
14	Partially correct	205 ms	616 KB	Partially correct
15	Partially correct	181 ms	604 KB	Partially correct
16	Partially correct	178 ms	608 KB	Partially correct
17	Partially correct	181 ms	608 KB	Partially correct
18	Partially correct	178 ms	600 KB	Partially correct
19	Partially correct	178 ms	604 KB	Partially correct
20	Correct	185 ms	612 KB	Output is correct
21	Correct	178 ms	604 KB	Output is correct
22	Partially correct	199 ms	608 KB	Partially correct
23	Partially correct	208 ms	624 KB	Partially correct
24	Partially correct	200 ms	600 KB	Partially correct
25	Partially correct	201 ms	604 KB	Partially correct
26	Partially correct	201 ms	856 KB	Partially correct
27	Partially correct	209 ms	612 KB	Partially correct
28	Partially correct	201 ms	604 KB	Partially correct
29	Partially correct	178 ms	600 KB	Partially correct
30	Partially correct	180 ms	612 KB	Partially correct
31	Partially correct	179 ms	604 KB	Partially correct
32	Correct	185 ms	608 KB	Output is correct
33	Correct	178 ms	604 KB	Output is correct
34	Correct	179 ms	600 KB	Output is correct
35	Partially correct	184 ms	600 KB	Partially correct
36	Correct	22 ms	344 KB	Output is correct