Submission #940931

#	Time	Username	Problem	Language	Result	Execution time	Memory
940931		socpite	Toxic Gene (NOI23_toxic)	C++17	21 / 100	6 ms	500 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 {
            int tot1 = query_sample(species);
			if(tot1 == species.size()){
				species.push_back(l);
				int tot2 = query_sample(species);
				for(int j = 0; j < sampling.size(); j++){
					if(tot2&(1<<j)){
						answer_type(sampling[j], 'S');
						done[sampling[j]] = 1;
					}
					else answer_type(sampling[j], 'R');
				}
			}
			else {
			// 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;
					}
					else {
						if(query_sample({sampling[j]}))answer_type(sampling[j], 'R');
						else answer_type(sampling[j], 'T');
					}
				}
			}	
			sampling = {vec[i]};
			species = {vec[i]};
			d = 1;
        }
    }
	int tot1 = query_sample(species);
	if(tot1 == species.size()){
		species.push_back(l);
		int tot2 = query_sample(species);
		for(int j = 0; j < sampling.size(); j++){
			if(tot2&(1<<j)){
				answer_type(sampling[j], 'S');
				done[sampling[j]] = 1;
			}
			else answer_type(sampling[j], 'R');
		}
	}
	else {
	// 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;
			}
			else {
				if(query_sample({sampling[j]}))answer_type(sampling[j], 'R');
				else answer_type(sampling[j], '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:31:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |    if(tot1 == species.size()){
      |       ~~~~~^~~~~~~~~~~~~~~~~
toxic.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int j = 0; j < sampling.size(); j++){
      |                    ~~^~~~~~~~~~~~~~~~~
toxic.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int j = 0; j < sampling.size(); j++){
      |                    ~~^~~~~~~~~~~~~~~~~
toxic.cpp:61:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  if(tot1 == species.size()){
      |     ~~~~~^~~~~~~~~~~~~~~~~
toxic.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int j = 0; j < sampling.size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~~
toxic.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for(int j = 0; j < sampling.size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 21 / 100