Submission #977644

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
977644	2024-05-08T08:16:04 Z	CSQ31	Toxic Gene (NOI23_toxic)	C++17	70.3 / 100	9 ms	688 KB

toxic

#include "toxic.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>tox;
#define sz(a) (int)(a.size())
mt19937 seed(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand2(int l,int r){return uniform_int_distribution<int>(l,r)(seed);}
vector<int>leftover;
void find_toxic(vector<int>v){
    //for(int x:v)cout<<x<<" ";
   //cout<<'\n';
    if(sz(v) == 1){
        //cout<<v[0]<<'\n';
        answer_type(v[0],'T');
        tox.push_back(v[0]);
        return;
    }
    int m = sz(v)/2;
    vector<int>a,b;
    for(int i=0;i<m;i++)a.push_back(v[i]);
    for(int i=m;i<sz(v);i++)b.push_back(v[i]);
	if(rand2(0,1))swap(a,b);

    int res = query_sample(a);
    if(res == sz(a)){ 
		for(int x:a)answer_type(x,'R');	
		find_toxic(b);
	}
    else {
		for(int x:b)leftover.push_back(x);
		find_toxic(a);
    }
}
void determine_type(int n){
	vector<int>p;
	for(int i=1;i<=n;i++)p.push_back(i);
	shuffle(p.begin(),p.end(),seed);
 
    tox.clear();
    vector<int>notoxic;
    for(int i=1;i<=n;i+=8){
        vector<int>v;
        for(int j=0;j<8;j++){
            if(i+j > n)break;
            for(int k=0;k<(1<<j);k++)v.push_back(p[i+j-1]);
        }
        //for(int x:v)cout<<x<<" ";
       //cout<<'\n';
        int res = query_sample(v);
        //cout<<res<<'\n';
        if(res == sz(v)){
            for(int j=0;j<8;j++){
                if(i+j > n)break;
                notoxic.push_back(p[i+j-1]);
            }
        }else{
            vector<int>u;
            for(int j=0;j<8;j++){
                if(i+j > n)break;
                if(res & (1<<j))answer_type(p[i+j-1],'S');
                else u.push_back(p[i+j-1]);
            }
			while(!u.empty()){
                //for(int x:u)cout<<x<<" ";
                //cout<<'\n';
				leftover.clear();
				find_toxic(u);
				u = leftover;
                if(u.empty() || query_sample(u) == sz(u)){
                    for(int x:u)answer_type(x,'R');
                    break;
                }
			}
        }
    }
    //for(int x:tox)cout<<x<<" ";
    //cout<<'\n';
    //for(int x:notoxic)cout<<x<<" ";
    //cout<<'\n';
    for(int i=0;i<sz(notoxic);i+=8){
        vector<int>v;
        for(int j=0;j<8;j++){
            if(i+j >= sz(notoxic))break;
            for(int k=0;k<(1<<j);k++)v.push_back(notoxic[i+j]);
 
        }
        v.push_back(tox[0]);
        int res = query_sample(v);
        for(int j=0;j<8;j++){
            if(i+j >= sz(notoxic))break;
            if(res & (1<<j))answer_type(notoxic[i+j],'S');
            else answer_type(notoxic[i+j],'R');
        }
    }
 
}

Subtask #1

70.3 / 100.0

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