Submission #886173

#	Time	Username	Problem	Language	Result	Execution time	Memory
886173		vjudge1	Toxic Gene (NOI23_toxic)	C++17	12.69 / 100	9 ms	516 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, int hmm){
	// cout << l << ' ' << r << ' ' << hmm << '\n'; 	
	if(l == r){
		if(query_sample(vector<int>{l}) == 0){
			T.pb(l);
			// cout << l << ' ';
			answer_type(l, 'T');
		}
		return;
	}
	vector<int> v;
	int m = l+r>>1;
	for(int i = l; i <= m; ++i) v.pb(i);
	int L = query_sample(v);
	if(hmm - (m - l + 1 - L) > 0) f(m+1, r, hmm - (m - l + 1 - L));
	if(L < m - l + 1) f(l, m, m - l + 1 - L);
}
void determine_type(int n){
	T.clear();
	vector<int> gg;
	for(int i = 1; i <= n; ++i) gg.pb(i);
	f(1, n, n - query_sample(gg));
	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, int)':
toxic.cpp:24:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |  int m = l+r>>1;
      |          ~^~
toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i = 0; i < a.size(); i += 8){
      |                 ~~^~~~~~~~~~

• Subtask 1: 12.692307689999998 / 100