답안 #952230

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
952230	2024-03-23T10:18:24 Z	gaga999	Toxic Gene (NOI23_toxic)	C++17	51.4 / 100	205 ms	864 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 = 0;
                double p = pow((nn - k / l - 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), 8);
        // 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");
            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

51.4 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	344 KB	Output is correct
2	Correct	188 ms	600 KB	Output is correct
3	Partially correct	189 ms	604 KB	Partially correct
4	Correct	187 ms	604 KB	Output is correct
5	Partially correct	193 ms	856 KB	Partially correct
6	Correct	190 ms	616 KB	Output is correct
7	Partially correct	191 ms	612 KB	Partially correct
8	Partially correct	205 ms	612 KB	Partially correct
9	Correct	190 ms	600 KB	Output is correct
10	Partially correct	191 ms	608 KB	Partially correct
11	Correct	194 ms	864 KB	Output is correct
12	Correct	189 ms	600 KB	Output is correct
13	Correct	189 ms	612 KB	Output is correct
14	Correct	193 ms	612 KB	Output is correct
15	Correct	189 ms	612 KB	Output is correct
16	Correct	191 ms	604 KB	Output is correct
17	Correct	193 ms	852 KB	Output is correct
18	Correct	190 ms	604 KB	Output is correct
19	Correct	189 ms	608 KB	Output is correct
20	Correct	196 ms	608 KB	Output is correct
21	Correct	186 ms	856 KB	Output is correct
22	Correct	190 ms	604 KB	Output is correct
23	Correct	188 ms	612 KB	Output is correct
24	Partially correct	188 ms	608 KB	Partially correct
25	Partially correct	188 ms	604 KB	Partially correct
26	Partially correct	192 ms	612 KB	Partially correct
27	Partially correct	187 ms	612 KB	Partially correct
28	Partially correct	188 ms	604 KB	Partially correct
29	Partially correct	190 ms	604 KB	Partially correct
30	Partially correct	194 ms	608 KB	Partially correct
31	Partially correct	189 ms	604 KB	Partially correct
32	Partially correct	189 ms	604 KB	Partially correct
33	Partially correct	189 ms	604 KB	Partially correct
34	Correct	188 ms	600 KB	Output is correct
35	Partially correct	189 ms	612 KB	Partially correct
36	Partially correct	23 ms	348 KB	Partially correct