Submission #828436

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
828436	2023-08-17T09:29:48 Z	반딧불(#10380)	Toxic Gene (NOI23_toxic)	C++17	91.9 / 100	31 ms	384 KB

toxic

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

using namespace std;

typedef long long ll;
const int G = 8, B = 8;

vector<int> searchRange;
vector<int> toxicVec, elseVec;
int know[302]; /// 1인지 2인지 알 때
int idx[302];
int ans[302]; /// 0: toxic, 1: regular, 2: strong
char chr[] = "TRS";

int query(vector<int> v){
	vector<int> v2;
	for(int x: v) v2.push_back(idx[x]);
	return query_sample(v2);
}

int queryRange(vector<int> vec, int l, int r){ /// 구간이 모두 독성이 아닌가?
	//printf("Queried "); for(int i=l; i<=r; i++) printf("%d ", vec[i]);
	//puts("");

	vector<int> vec2;
	for(int i=l; i<=r; i++) vec2.push_back(vec[i]);
	vec = vec2;

	vector<int> v;
	int cnt = 0;
	while((int)vec.size() < B && !elseVec.empty()) cnt++, vec.push_back(elseVec.back()), elseVec.pop_back();
	for(int i=0; i<(int)vec.size(); i++) for(int j=0; j<(1<<i); j++) v.push_back(vec[i]);
	int val = query(v), sz = (int)v.size();

	//printf("New vec: "); for(int x: vec) printf("%d ", x); puts("");
	//printf("New v: "); for(int x: v) printf("%d ", x); puts("");
	//printf("val: %d (expected %d)\n", val, sz);

	if(val != sz){
		for(int i=0; i<(int)vec.size(); i++) know[vec[i]] = 1 + ((val>>i)&1);
	}
	else while(cnt--) elseVec.push_back(vec.back()), vec.pop_back();
	return val == sz;
}

void findToxic(vector<int> &v){
	if((int)toxicVec.size() == 30) return;
	if(queryRange(v, 0, (int)v.size()-1)){
		for(int x: v) elseVec.push_back(x);
		return;
	}
	int L = 0, R = (int)v.size()-1;
	while(L<R){
		int M = (L+R)/2;
		if(queryRange(v, L, M)) L=M+1;
		else R=M;
	}
	toxicVec.push_back(v[L]);

	for(int i=0; i<L; i++) elseVec.push_back(v[i]);
	for(int i=L+1; i<(int)v.size(); i++) searchRange.push_back(v[i]);
}

void determine_type(int n){
	toxicVec.clear();
	elseVec.clear();
	searchRange.clear();
	memset(ans, 0, sizeof(ans));
	memset(know, 0, sizeof(know));

	for(int i=1; i<=n; i++) idx[i] = i, searchRange.push_back(i);
	srand(time(NULL));
	random_shuffle(idx+1, idx+n+1);
	//for(int i=1; i<=n; i++) printf("idx[%d] = %d\n", i, idx[i]);
	
	while(!searchRange.empty()){
		vector<int> v;
		for(int i=0; !searchRange.empty() && i<G; i++){
			v.push_back(searchRange[0]);
			searchRange.erase(searchRange.begin());
		}
		findToxic(v);
	}

	for(int i=1; i<=n; i++) ans[i] = 1;
	for(int x: toxicVec) ans[x] = 0;
	for(int i=1; i<=n; i++){
		if(!ans[i]) continue;
		if(know[i]) ans[i] = know[i];
		// else elseVec.push_back(i);
	}

	#ifdef TESTS
	printf("know: "); for(int i=1; i<=n; i++) printf("%d", know[i]);
	puts("");
	printf("ToxicVec: "); for(int x: toxicVec) printf("%d ", x);
	puts("");
	printf("ElseVec: "); for(int x: elseVec) printf("%d ", x);
	puts("");
	#endif

	int tox = toxicVec[0];
	for(int l=0; l<(int)elseVec.size(); l+=B){
		int r = min(l+B-1, (int)elseVec.size()-1);
		int d = r-l+1;
		vector<int> v (1, tox);
		for(int i=0; i<d; i++) for(int j=0; j<(1<<i); j++) v.push_back(elseVec[l+i]);
		int val = query(v);
		for(int i=0; i<d; i++) if((val>>i)&1) ans[elseVec[l+i]] = 2;
	}

	for(int i=1; i<=n; i++) answer_type(idx[i], chr[ans[i]]);
}

Subtask #1

91.9 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Partially correct	15 ms	376 KB	Partially correct
3	Partially correct	15 ms	368 KB	Partially correct
4	Correct	15 ms	380 KB	Output is correct
5	Partially correct	19 ms	372 KB	Partially correct
6	Partially correct	24 ms	376 KB	Partially correct
7	Partially correct	19 ms	372 KB	Partially correct
8	Partially correct	18 ms	364 KB	Partially correct
9	Partially correct	18 ms	384 KB	Partially correct
10	Partially correct	18 ms	376 KB	Partially correct
11	Correct	21 ms	340 KB	Output is correct
12	Correct	16 ms	380 KB	Output is correct
13	Correct	17 ms	352 KB	Output is correct
14	Partially correct	15 ms	372 KB	Partially correct
15	Partially correct	18 ms	340 KB	Partially correct
16	Partially correct	18 ms	376 KB	Partially correct
17	Partially correct	19 ms	340 KB	Partially correct
18	Partially correct	18 ms	372 KB	Partially correct
19	Partially correct	18 ms	376 KB	Partially correct
20	Partially correct	31 ms	340 KB	Partially correct
21	Partially correct	31 ms	340 KB	Partially correct
22	Correct	24 ms	340 KB	Output is correct
23	Correct	17 ms	372 KB	Output is correct
24	Correct	15 ms	384 KB	Output is correct
25	Partially correct	19 ms	300 KB	Partially correct
26	Correct	15 ms	380 KB	Output is correct
27	Correct	15 ms	372 KB	Output is correct
28	Correct	15 ms	376 KB	Output is correct
29	Partially correct	18 ms	380 KB	Partially correct
30	Partially correct	18 ms	376 KB	Partially correct
31	Partially correct	18 ms	376 KB	Partially correct
32	Partially correct	19 ms	340 KB	Partially correct
33	Partially correct	21 ms	340 KB	Partially correct
34	Partially correct	20 ms	340 KB	Partially correct
35	Partially correct	25 ms	372 KB	Partially correct
36	Partially correct	3 ms	212 KB	Partially correct