Submission #941052

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
941052	2024-03-08T05:58:56 Z	bachhoangxuan	Toxic Gene (NOI23_toxic)	C++17	93.25 / 100	28 ms	748 KB

toxic

#include "toxic.h"
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(69420);

vector<int> toxic;
void reset(){
    toxic.clear();
}
void add(int x,int cnt){
    for(int i=0;i<cnt;i++) toxic.push_back(x);
}
int ask(){
    return query_sample(toxic);
}

void determine_type(int n){
	vector<int> p(n);
    vector<char> c(n+1);
    iota(p.begin(),p.end(),1);
    //reverse(p.begin(),p.end());
    vector<int> all;
    int T=0;
    while(!p.empty()){
        shuffle(p.begin(),p.end(),rng);
        vector<int> cur;
        for(int i=0;i<8;i++){
            if(p.empty()) break;
            cur.push_back(p.back());
            p.pop_back();
        }
        reset();
        int sz=(int)cur.size();
        for(int i=0;i<sz;i++) add(cur[i],(1<<i));
        int total=ask();
        /*
        cout << (int)cur.size() << '\n';
        for(int x:cur) cout << x << ' ';
        cout << total << '\n';
        */
        if(total==(1<<sz)-1) all.insert(all.end(),cur.begin(),cur.end());
        else{
            for(int i=sz-1;i>=0;i--){
                if((total>>i)&1){
                    c[cur[i]]='S';
                    cur.erase(cur.begin()+i);
                }
            }
            sz=(int)cur.size();
            int l=0,r=sz-2,pos=sz-1;
            while(l<=r){
                int mid=(l+r)>>1;reset();
                for(int i=0;i<=mid;i++) add(cur[i],1<<i);

                int num=mid+1;
                vector<int> nxt;
                //cout << "all " << (int)all.size() << '\n';
                while(!all.empty() && num+(int)nxt.size()<8){
                    add(all.back(),1<<(num+(int)nxt.size()));
                    nxt.push_back(all.back());all.pop_back();
                }

                int cnt=ask(),real_cnt=cnt&((1<<num)-1);
                if(!real_cnt){
                    for(int i=0;i<(int)nxt.size();i++){
                        if(cnt>>(num+i)&1) c[nxt[i]]='S';
                        else c[nxt[i]]='R';
                    }
                }
                else all.insert(all.end(),nxt.begin(),nxt.end());
                cnt=real_cnt;
                //cout << "cnt " << cnt << '\n';
                if(cnt==0) pos=mid,r=mid-1;
                else l=mid+1;
            }

            //cout << '*' << pos << '\n';

            T=cur[pos];
            c[cur[pos]]='T';
            cur.erase(cur.begin()+pos);
            for(int i=pos-1;i>=0;i--){
                c[cur[i]]='R';
                cur.erase(cur.begin()+i);
            }
            p.insert(p.begin(),cur.begin(),cur.end());
        }
    }
    while(!all.empty()){
        vector<int> cur;
        for(int i=0;i<8;i++){
            if(all.empty()) break;
            cur.push_back(all.back());
            all.pop_back();
        }
        reset();
        add(T,1);
        int sz=(int)cur.size();
        for(int i=0;i<sz;i++) add(cur[i],(1<<i));
        int total=ask();
        for(int i=sz-1;i>=0;i--){
            if(total>>i&1) c[cur[i]]='S';
            else c[cur[i]]='R';
        }
    }
    //for(int i=1;i<=n;i++) cout << c[i];
    //cout << '\n';
    for(int i=1;i<=n;i++) answer_type(i,c[i]);
}

Subtask #1

93.25 / 100.0

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