Submission #952075

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
952075	2024-03-23T05:04:46 Z	gaga999	Toxic Gene (NOI23_toxic)	C++17	30.4706 / 100	53 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);

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 = 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');
    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]);
    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

30.47058824 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Partially correct	49 ms	616 KB	Partially correct
3	Partially correct	50 ms	608 KB	Partially correct
4	Partially correct	48 ms	604 KB	Partially correct
5	Partially correct	46 ms	600 KB	Partially correct
6	Partially correct	46 ms	856 KB	Partially correct
7	Partially correct	46 ms	600 KB	Partially correct
8	Partially correct	49 ms	604 KB	Partially correct
9	Partially correct	46 ms	604 KB	Partially correct
10	Partially correct	45 ms	604 KB	Partially correct
11	Partially correct	42 ms	604 KB	Partially correct
12	Partially correct	53 ms	600 KB	Partially correct
13	Partially correct	48 ms	600 KB	Partially correct
14	Partially correct	49 ms	604 KB	Partially correct
15	Partially correct	46 ms	604 KB	Partially correct
16	Partially correct	45 ms	604 KB	Partially correct
17	Partially correct	45 ms	600 KB	Partially correct
18	Partially correct	45 ms	608 KB	Partially correct
19	Partially correct	45 ms	600 KB	Partially correct
20	Partially correct	44 ms	604 KB	Partially correct
21	Partially correct	45 ms	604 KB	Partially correct
22	Partially correct	46 ms	604 KB	Partially correct
23	Partially correct	46 ms	604 KB	Partially correct
24	Partially correct	52 ms	600 KB	Partially correct
25	Partially correct	48 ms	600 KB	Partially correct
26	Partially correct	49 ms	604 KB	Partially correct
27	Partially correct	48 ms	600 KB	Partially correct
28	Partially correct	48 ms	604 KB	Partially correct
29	Partially correct	47 ms	600 KB	Partially correct
30	Partially correct	48 ms	600 KB	Partially correct
31	Partially correct	46 ms	604 KB	Partially correct
32	Partially correct	44 ms	856 KB	Partially correct
33	Partially correct	42 ms	600 KB	Partially correct
34	Partially correct	50 ms	600 KB	Partially correct
35	Partially correct	45 ms	604 KB	Partially correct
36	Partially correct	6 ms	344 KB	Partially correct