Submission #952066

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
952066	2024-03-23T04:56:16 Z	gaga999	Toxic Gene (NOI23_toxic)	C++17	6.95385 / 100	40 ms	600 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
    {
        if (size(qy) == 1)
        {
            // db("okk");
            // 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)
        {
            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(8, size(cr)); // dp[size(cr)][k];
        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);
            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');
    // while (!qs.empty())
    //     qry(vector<int>(1, pos));
    // for (int i = 1; i <= n; i++)
    //     assert(vd[i]);
    vector<int> qq(2, pos);
    for (int i = 1; i <= n; i++)
    {
        if (vd[i])
            continue;
        qq[1] = i;
        int res = query_sample(qq);
        if (!res)
            answer_type(i, 'R');
        else
            answer_type(i, 'S');
    }
    // assert(pos);
}

// signed main() {}

Compilation message

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

Subtask #1

6.95384615 / 100.0

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