Submission #940968

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
940968	2024-03-08T03:38:31 Z	hotboy2703	Toxic Gene (NOI23_toxic)	C++17	29.9529 / 100	9 ms	760 KB

toxic

#include "toxic.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
ll ans[310];
//0 thuong 1 doc 2 manh
ll wow = 0;
ll query(vector <ll> all){
    wow++;
    return query_sample(all);
}
//0 thuong 1 doc 2 manh
void solve(vector <ll> all){
    if (sz(all) == 1){ans[all.back()]=1;return;}
    ll mid = sz(all)/2;
    vector <ll> L;
    vector <ll> R;
    for (ll i = 0;i < mid;i++)L.push_back(all[i]);
    for (ll i = mid;i < sz(all);i ++)R.push_back(all[i]);
    if (query(L)!=sz(L)){
        solve(L);
        if (query(R) != sz(R))solve(R);
    }
    else solve(R);
}
void determine_type(int n){
    for (ll i = 1;i <= n;i ++)ans[i] = -1;
	for (ll i = 1;i <= n;i += 8){
        vector <ll> all;
        for (ll j = 0;j < 8 && i + j <= n;j ++){
            for (ll k = 0;k < MASK(j);k ++)all.push_back(i+j);
        }
        ll sus = query(all);
//        for (auto x:all)cout<<x<<' ';
//        cout<<endl;
        if (sus!=sz(all)){
//            cout<<sus<<endl;
            vector <ll> tmp;
            for (ll j = 0;j < 8 && i + j <= n;j ++){
                tmp.push_back(i+j);
                if (BIT(sus,j))ans[i+j] = 2;
            }
            solve(tmp);
        }
	}
	ll poison = -1;
	vector <ll> rem;
    for (ll i = 1;i <= n;i ++){
//        cout<<ans[i]<<' ';
        if (ans[i] == 1){
            poison = i;
        }
        else{
            if (ans[i] == -1)rem.push_back(i);
        }
    }
//    for (auto x:rem)cout<<x<<' ';
//    cout<<'\n';
    while (sz(rem)){
        vector <ll> cur;
        while (sz(rem) && sz(cur) < 8){cur.push_back(rem.back());rem.pop_back();}
        vector <ll> all;
        for (ll j = 0;j < sz(cur);j ++){
            for (ll k = 0;k < MASK(j);k ++){
                all.push_back(cur[j]);
            }
        }
        all.push_back(poison);
        ll x = query(all);
        for (ll j = 0;j < sz(cur);j ++){
            if (BIT(x,j)){
                ans[cur[j]] = 2;
            }
            else ans[cur[j]] = 0;
        }
    }
    for (ll i = 1;i <= n;i ++){
        if (ans[i]==0)answer_type(i,'R');
        if (ans[i]==2)answer_type(i,'S');
        if (ans[i]==1)answer_type(i,'T');
    }
}

Subtask #1

29.95294118 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Partially correct	8 ms	348 KB	Partially correct
3	Partially correct	7 ms	508 KB	Partially correct
4	Partially correct	8 ms	348 KB	Partially correct
5	Partially correct	8 ms	760 KB	Partially correct
6	Partially correct	8 ms	348 KB	Partially correct
7	Partially correct	8 ms	348 KB	Partially correct
8	Partially correct	8 ms	348 KB	Partially correct
9	Partially correct	8 ms	512 KB	Partially correct
10	Partially correct	8 ms	348 KB	Partially correct
11	Partially correct	8 ms	348 KB	Partially correct
12	Partially correct	7 ms	348 KB	Partially correct
13	Partially correct	8 ms	348 KB	Partially correct
14	Partially correct	7 ms	348 KB	Partially correct
15	Partially correct	8 ms	348 KB	Partially correct
16	Partially correct	8 ms	508 KB	Partially correct
17	Partially correct	8 ms	348 KB	Partially correct
18	Partially correct	8 ms	348 KB	Partially correct
19	Partially correct	9 ms	348 KB	Partially correct
20	Partially correct	8 ms	512 KB	Partially correct
21	Partially correct	8 ms	348 KB	Partially correct
22	Partially correct	8 ms	348 KB	Partially correct
23	Partially correct	7 ms	348 KB	Partially correct
24	Correct	7 ms	348 KB	Output is correct
25	Correct	7 ms	344 KB	Output is correct
26	Correct	8 ms	348 KB	Output is correct
27	Correct	7 ms	504 KB	Output is correct
28	Correct	7 ms	348 KB	Output is correct
29	Correct	7 ms	348 KB	Output is correct
30	Correct	8 ms	512 KB	Output is correct
31	Correct	7 ms	508 KB	Output is correct
32	Correct	7 ms	500 KB	Output is correct
33	Correct	7 ms	344 KB	Output is correct
34	Partially correct	8 ms	348 KB	Partially correct
35	Partially correct	8 ms	348 KB	Partially correct
36	Partially correct	1 ms	348 KB	Partially correct