Submission #1185686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185686		mychecksedad	Toxic Gene (NOI23_toxic)	C++20	89.20 / 100	15 ms	748 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=  0;
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;
vi bad;
void send(int ps, char c){
	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;
	bool ayn_found = false;

	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()){
			if(ayn_found){
				for(int j = 0; j < v.size(); ++j){
					if(!found[v[j]]){
						send(v[j], 'R');
					}
				}
			}
			if(!ayn_found) return -1;
			return 31;
		}
		ayn_found = true;
		vi rem;
		for(int j = 0; j < n; ++j){
			if((1<<j)&num) {
				send(v[j], 'S');
				rem.pb(j);
			}
		}
		reverse(all(rem));
		for(int x: rem) v.erase(v.begin()+x);

		// if(query(get_vector_range(v, l, r)) == r - l + 1) return (pos == -1 ? -1 : v[pos]);
		n = v.size();
		l = 0;
		r = n - 2;
		res = n - 1;

		while(l <= r){
			int mid = l+r>>1;
			vi bad_5, bad5;
			int e = mid - l + 1, ee = 0;
			while(bad.size() && bad_5.size() + e + (mid-l+1) <= 300){
				for(int i = 0; i < e; ++i) bad_5.pb(bad.back()); 
				bad5.pb(bad.back());
				bad.pop_back();
				e *= 2;
				++ee;
			}
			vi ragne = get_vector_range(v, l, mid);
			for(int x: bad_5) ragne.pb(x);
			int num = query(ragne);


			if(num == ragne.size()){
				l = mid + 1;
				for(int x: bad5) bad.pb(x);
			}else{
				num = num / (mid - l + 1);
				for(int i = 0; i < ee; ++i){
					if((num&(1<<i))){
						send(bad5[i], 'S');
					}else{
						send(bad5[i], 'R');
					}
				}
				res = mid;
				r = mid - 1;
			}
		}
		pos = res;
		for(int j = 0; j < pos; ++j){
			if(!found[v[j]]) send(v[j], 'R');
		}
		send(v[pos], 'T');
		y = v[pos];
		for(int j = 0; j <= pos; ++j) v.erase(v.begin());
		n = v.size();
		pos = -1;
		// cout << n << ' ' << pos << '\n';
	}
	
	if(pos != -1){
		for(int j = 0; j < v.size(); ++j){
			if(!found[v[j]]){
				send(v[j], 'R');
			}
		}
	}
	return 31;
}

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