Submission #1185652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185652		mychecksedad	Toxic Gene (NOI23_toxic)	C++20	64.90 / 100	11 ms	744 KiB

toxic

/* Author : Mychecksdead  */
#include "toxic.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rn(int l, int r){
	return uniform_int_distribution<int>(l,r)(rng);
}

int qq, y;
int query(vi v){
	vi u;
	if(qq > 250){
		assert(false);
	}
	++qq;
	for(int x: v) u.pb(x+1);
	return query_sample(u);
}

vi get_vector_range(vi v, int l, int r){
	vi res;
	for(int j = l; j <= r; ++j) res.pb(v[j]);
	return res;
}
bitset<N> found;
void send(int ps, char c){
	if(found[ps]) return;
	found[ps] = 1;
	answer_type(ps + 1, c);
}
void send(int ps, char c, char mm){
	if(found[ps]) return;
	found[ps] = 1;
	answer_type(ps + 1, c);
}


int identify(vi &v){ // there is certainly 1 in v
	int n = v.size();
	int pos = -1;

	while(pos + 1 < n){
		int l = pos + 1, r = n - 1, res = n - 1;
		
		vi U;
		for(int j = l; j <= r; ++j){
			for(int i = 0; i < (1<<j); ++i) U.pb(v[j]);
		}
		// for(int x: U) cout << x << ' ';
		int num = query(U);
		// cout << U.size() << ' ' << toxic << '\n';
		if(num == U.size()){
			v.clear();
			return pos == -1 ? -1 : v[pos];
		}
		for(int j = l; j <= r; ++j){
			if((1<<j)&num) send(v[j], 'S');
		}


		// if(query(get_vector_range(v, l, r)) == r - l + 1) return (pos == -1 ? -1 : v[pos]);

		r = n - 2;
		res = n - 1;

		while(l <= r){
			int mid = l+r>>1;
			if(query(get_vector_range(v, l, mid)) == mid - l + 1){
				l = mid + 1;
			}else{
				res = mid;
				r = mid - 1;
			}
		}
		pos = res;
		// cout << v[pos] << " toxic\n";
		send(v[pos], 'T');
		y = v[pos];
		for(int j = 0; j < pos; ++j){
			if(!found[v[j]]){
				send(v[j], 'R', 'm');
			}
		}
		for(int j = 0; j <= pos; ++j) v.erase(v.begin());
		for(int j = 0; j < v.size(); ++j){
			if(found[v[j]]){
				v.erase(v.begin() + j);
				--j;
			}
		}
		return -1;
	}
	assert(false);
	return -1;
}

void identify_stronq(vi v, int toxic){
	vi U;
	U.pb(toxic);
	for(int j = 0; j < v.size(); ++j){
		for(int i = 0; i < (1<<j); ++i) U.pb(v[j]);
	}
	// for(int x: U) cout << x << ' ';
	int num = query(U);
	// cout << U.size() << ' ' << toxic << '\n';
	for(int j = 0; j < v.size(); ++j){
		if((1<<j)&num) send(v[j], 'S');
		else send(v[j], 'R');
	}
}

void determine_type(int n){
	y = 0;
	qq = 0;
	found = 0;
	vi C;
	for(int i = 0; i < n; ++i){
		C.pb(i);
		swap(C[i], C[rn(0,i)]);
	}
	vi V;
	for(int i = 0; i < n; i++){
		V.pb(C[i]);
		if(V.size() == 8){
			identify(V);
		}
	}
	while(!V.empty()) identify(V);
	vi A;
	for(int i = 0; i < n; ++i) if(!found[i]) A.pb(i);
	for(int i = 0; i < A.size(); i += 8){
		vi v;
		for(int j = i; j < min(i + 8, int(A.size())); ++j) v.pb(A[j]);
		identify_stronq(v, y);
	}
}

• Subtask 1: 64.9 / 100