Submission #940912

#	Time	Username	Problem	Language	Result	Execution time	Memory
940912		socpite	Toxic Gene (NOI23_toxic)	C++17	8.84 / 100	6 ms	688 KiB

toxic

#include<bits/stdc++.h>
#include"toxic.h"
using namespace std;

int query_sample(vector<int> species);

void determine_type(int n){
    int l = 1, r = n;
    vector<int> vec(n);
    vector<bool> done(n+1, 0);
    iota(vec.begin(), vec.end(), 1);
    while(l < r){
        int mid = (l+r)>>1;
		int tmp = query_sample(vector<int>(vec.begin() + l - 1, vec.begin() + mid));
        if(tmp != mid - l + 1)r = mid;
        else l = mid+1;
    }
    vec.erase(vec.begin() + l - 1);
    answer_type(l, 'T');
    int d = 0;
    vector<int> sampling;
    vector<int> species;
    for(int i = 0; i < vec.size(); i++){
        if(species.size() + (1<<d) < 300){
            for(int _ = 0; _ < (1<<d); _++)species.push_back(vec[i]);
            sampling.push_back(vec[i]);
            d++;
        }
        else {
			species.push_back(l);
            int tot1 = query_sample(species);
			// cout << tot1 << " " << tot2 << endl;
            for(int j = 0; j < sampling.size(); j++){
                if(tot1&(1<<j)){
                    answer_type(sampling[j], 'S');
                    done[sampling[j]] = 1;
                }
            }
            sampling = {vec[i]};
            species = {vec[i]};
            d = 1;
        }
    }
	species.push_back(l);
	int tot1 = query_sample(species);
	// cout << tot1 << " " << tot2 << endl;
	for(int j = 0; j < sampling.size(); j++){
		if(tot1&(1<<j)){
			answer_type(sampling[j], 'S');
			done[sampling[j]] = 1;
		}
	}
    for(int i = 1; i <= n; i++){
        if(done[i])vec.erase(find(vec.begin(), vec.end(), i));
    }
    for(auto v: vec){
        if(query_sample({v}))answer_type(v, 'R');
        else answer_type(v, 'T');
    }
}

Compilation message (stderr)

toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i = 0; i < vec.size(); i++){
      |                    ~~^~~~~~~~~~~~
toxic.cpp:33:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             for(int j = 0; j < sampling.size(); j++){
      |                            ~~^~~~~~~~~~~~~~~~~
toxic.cpp:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int j = 0; j < sampling.size(); j++){
      |                 ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 8.83846154 / 100