Submission #1185555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185555		mychecksedad	Toxic Gene (NOI23_toxic)	C++20	46 / 100	8 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;
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){
	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;
		

		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');
	}
	if(pos==-1) return -1;
	return v[pos];
}

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){
	int 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)]);
	}
	for(int i = 0; i < n; i += 7){
		vi v;
		for(int j = i; j < min(i+7, n); ++j) v.pb(C[j]);
		int x = identify(v);
		if(x != -1){
			y = x;
		}
	}
	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: 46 / 100