oj.uz

Submission #828345

# Submission time Handle Problem Language Result Execution time Memory
828345 2023-08-17T08:42:44 Z 반딧불(#10380) Toxic Gene (NOI23_toxic) C++17
43.6706 / 100
 11 ms 384 KB 
#include "toxic.h"
#include <bits/stdc++.h>

using namespace std;

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

vector<int> toxicVec, elseVec;
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(int l, int r){
	vector<int> v;
	for(int i=l; i<=r; i++) v.push_back(i);
	return query(v);
}

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

	vector<int> v2;
	for(int i=L+1; i<(int)v.size(); i++) v2.push_back(v[i]);
	if(!v2.empty()) findToxic(v2);
}

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

	for(int i=1; i<=n; i++) idx[i] = i;
	random_shuffle(idx+1, idx+n+1);

	for(int l=1; l<=n; l+=G){
		int r = min(l+G-1, n);
		vector<int> v;
		for(int i=l; i<=r; i++) v.push_back(i);
		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]) elseVec.push_back(i);

	#ifdef TESTS
	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
43.67058824 / 100.0

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