Submission #886118

#	Time	Username	Problem	Language	Result	Execution time	Memory
886118		vjudge1	Toxic Gene (NOI23_toxic)	C++17	3.99 / 100	4 ms	600 KiB

toxic

#include "toxic.h"
#include <bits/stdc++.h>

#define lli long long int
#define MP make_pair
#define REP(i,n) for(int (i); (i)<(n); (i)++)
#define pb push_back

const int N = 305;

const int MOD = 1e9+7;
constexpr lli INF = 1e17;
using namespace std;

void fastio() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<char> typ(N, 'X');
int ex;
void solve(vector<int> &cur, int cnt) {
	int sz = cur.size();
	if(!sz) return;
	if(sz == 1) {
		if(cnt) {
			typ[cur[0]] = 'S';
		}
		else {
			typ[cur[0]] = 'R';
		}
		return;
	}
	
	if(cnt == sz) {
		for(auto c : cur) {
			typ[c] = 'S';
		}
		return;
	}
	if(cnt == 0) {
		for(auto c : cur) {
			typ[c] = 'R';
		}
		return;
	}
	vector<int> nw;
	for(int i = 0; i<sz/2; i++) {
		nw.pb(cur.back());
		cur.pop_back();
	}
	cur.pb(ex);
	int nxt = query_sample(cur);
	cur.pop_back();
	solve(cur, nxt);
	solve(nw, cnt - nxt);
	
}
void determine_type(int n){
	

	vector<int> nont;

	for(int i = 1 ;i<=n; i++) {
		if(!query_sample({i})) {
			typ[i] = 'T';
			ex = i;
		}
		else {
			nont.pb(i);
		}
	}	
	shuffle(nont.begin(), nont.end(), rng);
	nont.pb(ex);
	int cnt = query_sample(nont);
	nont.pop_back();
	solve(nont, cnt); 
	for(int i = 1; i<=n; i++) {
		answer_type(i, typ[i]);
	}
}

• Subtask 1: 3.99230769 / 100