oj.uz

Submission #977617

# Submission time Handle Problem Language Result Execution time Memory
977617 2024-05-08T07:41:23 Z CSQ31 Toxic Gene (NOI23_toxic) C++17
34.6118 / 100
 7 ms 512 KB 
#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());
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;
    }
	if(sz(tox) == 30){
        for(int x:v)answer_type(x,'R');
        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]);

    int res = query_sample(a);
    if(res == sz(a)){ for(int x:a)answer_type(x,'R');}
    else find_toxic(a);

    res = query_sample(b);
    if(res == sz(b)){ for(int x:b)answer_type(x,'R');}
    else find_toxic(b);
}
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;
	vector<int>u;
    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{
            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]);
            }
           // for(int x:u)cout<<x<<" ";
            //cout<<'\n';
            //cout<<"TES"<<'\n';
        }
    }
    int m = max(1,sz(u)/42);
	for(int i=0;i<sz(u);i+=m){
		vector<int>tmp;
		for(int j=0;j<m;j++){
			if(i+j >= sz(u))break;
			tmp.push_back(u[i+j]);
		}
        int res = query_sample(tmp);
        if(res == sz(tmp)){
            for(int x:tmp)answer_type(x,'R');
            continue;
        }
		find_toxic(tmp);
	}
    //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
34.61176471 / 100.0

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