Submission #828284

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
828284	2023-08-17T07:45:03 Z	박상훈(#10381)	Toxic Gene (NOI23_toxic)	C++17	63.55 / 100	11 ms	516 KB

toxic

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

using namespace std;
typedef long long ll;

int I[303];
mt19937 seed(1557);

pair<vector<int>, vector<int>> query_exp(const vector<int> &V, const vector<int> &W){
	vector<int> Q;
	for (int i=0;i<(int)V.size();i++){
		for (int j=0;j<(1<<i);j++) Q.push_back(V[i]);
	}

	for (int i=0;i<(int)W.size();i++) Q.push_back(W[i]);

	for (auto &x:Q) x = I[x];
	int ret = query_sample(Q);
	vector<int> dead, alive;

	for (int i=0;i<(int)V.size();i++){
		if (ret&(1<<i)) alive.push_back(V[i]);
		else dead.push_back(V[i]);
	}

	return {dead, alive};
}

int query_linear(const vector<int> &V){
	vector<int> Q;
	for (auto &x:V) Q.push_back(I[x]);
	return query_sample(Q);
}

int search(const vector<int> &dead){
	int l = 0, r = (int)dead.size()-1;
	while(l<r){
		int m = (l+r)>>1;
		vector<int> V;
		for (int i=l;i<=m;i++) V.push_back(dead[i]);

		if (query_linear(V)==(int)V.size()) l = m+1;
		else r = m;
	}

	return dead[l];
}

void determine_type(int n){
	for (int i=1;i<=n;i++) I[i] = i;
	shuffle(I+1, I+n+1, seed);
	
	vector<char> typ(n+1);
	vector<int> toxic;
	vector<pair<int, int>> P;

	for (int i=1;i<=n;i+=8){
		int r = min(n, i+7);

		vector<int> V;
		for (int j=i;j<=r;j++) V.push_back(j);
		
		auto [dead, alive] = query_exp(V, vector<int>());
		if (dead.empty()){P.emplace_back(i, r); continue;}

		for (auto &x:alive) typ[x] = 'S';

		// printf("dead: ");
		// for (auto &x:dead) printf("%d ", x);
		// printf("\n");

		// printf("alive: ");
		// for (auto &x:alive) printf("%d ", x);
		// printf("\n");
		
		while(true){
			int p = search(dead);
			toxic.push_back(p);
			typ[p] = 'T';

			// printf("found toxic: %d\n", I[p]);

			dead.erase(find(dead.begin(), dead.end(), p));
			if (query_linear(dead)==(int)dead.size()) break;
		}

		for (auto &x:dead) typ[x] = 'R';
	}

	for (auto &[l, r]:P){
		vector<int> V;
		for (int j=l;j<=r;j++) V.push_back(j);

		auto [dead, alive] = query_exp(V, vector<int>(1, toxic[0]));
		for (auto &x:dead) typ[x] = 'R';
		for (auto &x:alive) typ[x] = 'S';
	}

	for (int i=1;i<=n;i++) answer_type(I[i], typ[i]);
}

Subtask #1

63.55 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Partially correct	9 ms	396 KB	Partially correct
3	Partially correct	9 ms	336 KB	Partially correct
4	Partially correct	9 ms	340 KB	Partially correct
5	Partially correct	10 ms	388 KB	Partially correct
6	Partially correct	9 ms	340 KB	Partially correct
7	Partially correct	9 ms	392 KB	Partially correct
8	Partially correct	9 ms	352 KB	Partially correct
9	Partially correct	9 ms	340 KB	Partially correct
10	Partially correct	9 ms	340 KB	Partially correct
11	Partially correct	8 ms	340 KB	Partially correct
12	Partially correct	9 ms	348 KB	Partially correct
13	Partially correct	9 ms	392 KB	Partially correct
14	Partially correct	9 ms	340 KB	Partially correct
15	Partially correct	9 ms	340 KB	Partially correct
16	Partially correct	9 ms	396 KB	Partially correct
17	Partially correct	9 ms	388 KB	Partially correct
18	Partially correct	9 ms	340 KB	Partially correct
19	Partially correct	9 ms	340 KB	Partially correct
20	Partially correct	9 ms	340 KB	Partially correct
21	Partially correct	8 ms	380 KB	Partially correct
22	Correct	8 ms	396 KB	Output is correct
23	Correct	9 ms	516 KB	Output is correct
24	Partially correct	9 ms	344 KB	Partially correct
25	Partially correct	9 ms	340 KB	Partially correct
26	Partially correct	9 ms	340 KB	Partially correct
27	Partially correct	9 ms	340 KB	Partially correct
28	Partially correct	9 ms	340 KB	Partially correct
29	Partially correct	9 ms	340 KB	Partially correct
30	Partially correct	9 ms	396 KB	Partially correct
31	Partially correct	9 ms	400 KB	Partially correct
32	Partially correct	9 ms	340 KB	Partially correct
33	Partially correct	8 ms	348 KB	Partially correct
34	Partially correct	11 ms	340 KB	Partially correct
35	Partially correct	11 ms	400 KB	Partially correct
36	Partially correct	1 ms	212 KB	Partially correct