Submission #886118

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
886118	2023-12-11T13:26:01 Z	vjudge1	Toxic Gene (NOI23_toxic)	C++17	3.99231 / 100	4 ms	600 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Partially correct	1 ms	348 KB	Partially correct
3	Partially correct	2 ms	348 KB	Partially correct
4	Partially correct	3 ms	348 KB	Partially correct
5	Partially correct	1 ms	348 KB	Partially correct
6	Partially correct	2 ms	348 KB	Partially correct
7	Partially correct	2 ms	348 KB	Partially correct
8	Partially correct	2 ms	512 KB	Partially correct
9	Partially correct	4 ms	348 KB	Partially correct
10	Partially correct	3 ms	600 KB	Partially correct
11	Partially correct	3 ms	504 KB	Partially correct
12	Partially correct	1 ms	348 KB	Partially correct
13	Partially correct	2 ms	344 KB	Partially correct
14	Partially correct	4 ms	348 KB	Partially correct
15	Partially correct	1 ms	348 KB	Partially correct
16	Partially correct	2 ms	504 KB	Partially correct
17	Partially correct	2 ms	348 KB	Partially correct
18	Partially correct	2 ms	348 KB	Partially correct
19	Partially correct	3 ms	348 KB	Partially correct
20	Partially correct	3 ms	348 KB	Partially correct
21	Partially correct	3 ms	600 KB	Partially correct
22	Partially correct	3 ms	348 KB	Partially correct
23	Partially correct	1 ms	348 KB	Partially correct
24	Partially correct	1 ms	348 KB	Partially correct
25	Partially correct	2 ms	348 KB	Partially correct
26	Partially correct	2 ms	348 KB	Partially correct
27	Partially correct	3 ms	344 KB	Partially correct
28	Partially correct	3 ms	360 KB	Partially correct
29	Partially correct	1 ms	348 KB	Partially correct
30	Partially correct	2 ms	348 KB	Partially correct
31	Partially correct	2 ms	348 KB	Partially correct
32	Partially correct	3 ms	348 KB	Partially correct
33	Partially correct	3 ms	348 KB	Partially correct
34	Partially correct	1 ms	348 KB	Partially correct
35	Partially correct	1 ms	348 KB	Partially correct
36	Partially correct	0 ms	348 KB	Partially correct