Submission #886188

#	Time	Username	Problem	Language	Result	Execution time	Memory
886188		vjudge1	Toxic Gene (NOI23_toxic)	C++17	37.20 / 100	7 ms	508 KiB

toxic

// #include "toxic.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define MOD 1000000007

int query_sample(std::vector<int> species);
void answer_type(int x, char c);
vector<int> T;
void f(int l, int r){
	if(l == r){
		T.pb(l);
		// cout << l << ' ';
		answer_type(l, 'T');
		return;
	}
	vector<int> v, v1;
	int m = l+r>>1;
	for(int i = l; i <= m; ++i) v.pb(i);
	for(int i = m+1; i <= r; ++i) v1.pb(i);
	int L = query_sample(v);
	int R = query_sample(v1);
	if(L < m - l + 1) f(l, m);
	if(R < r - m) f(m+1, r);
}
void determine_type(int n){
	T.clear();
	// f(1, n);
	for(int i = 1; i <= n; i += 3){
		vector<int> v;
		for(int j = i; j <= min(n, i+2); ++j) v.pb(j);
		int f = query_sample(v);
		if(f < v.size()){
			for(int j = 0; j < v.size(); ++j){
				if(query_sample(vector<int>{v[j]}) == 0){
					T.pb(v[j]); 
					answer_type(v[j], 'T');
				}
			}
		}
	}
	vector<bool> used(n+1);
	for(int x: T) used[x] = 1;
	vector<int> a;
	for(int i = 1; i <= n; ++i) if(!used[i]) a.pb(i);
	for(int i = 0; i < a.size(); i += 8){
		vector<int> cur;
		cur.pb(T[0]);
		for(int j = i; j < min(int(a.size()), i+8); ++j){
			for(int l = 0; l < (1<<(j-i)); ++l){
				cur.pb(a[j]);
			}
		}
		// assert(cur.size() <= 300);
		// cout << cur.size() << '\n';
		int s = query_sample(cur);
		for(int j = i; j < min(int(a.size()), i+8); ++j){
			int d = (j-i);
			if(s&(1<<d)){
				answer_type(a[j], 'S');
			}else answer_type(a[j], 'R');
		}
	}
}

Compilation message (stderr)

toxic.cpp: In function 'void f(int, int)':
toxic.cpp:21:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |  int m = l+r>>1;
      |          ~^~
toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:36:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   if(f < v.size()){
      |      ~~^~~~~~~~~~
toxic.cpp:37:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    for(int j = 0; j < v.size(); ++j){
      |                   ~~^~~~~~~~~~
toxic.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i = 0; i < a.size(); i += 8){
      |                 ~~^~~~~~~~~~

• Subtask 1: 37.2 / 100