oj.uz

Submission #828333

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

using namespace std;

typedef long long ll;
const int G = 4, 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);
}

bool findToxic(int l, int r, bool skip=0){
	if(!skip && queryRange(l, r) == r-l+1) return false;
	if((int)toxicVec.size() == 30) return false;
	if(l==r){
		toxicVec.push_back(l);
		return true;
	}
	int m = (l+r)/2;
	bool tmp = findToxic(l, m, 0);
	if((int)toxicVec.size() == 30) return tmp;
	findToxic(m+1, r, !tmp);
	return true;
}

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);
		findToxic(l, r);
	}

	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
42.11764706 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Partially correct 11 ms 340 KB Partially correct
3 Partially correct 7 ms 376 KB Partially correct
4 Partially correct 8 ms 376 KB Partially correct
5 Partially correct 7 ms 372 KB Partially correct
6 Partially correct 7 ms 368 KB Partially correct
7 Partially correct 7 ms 368 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 340 KB Partially correct
11 Partially correct 7 ms 340 KB Partially correct
12 Partially correct 7 ms 376 KB Partially correct
13 Partially correct 7 ms 380 KB Partially correct
14 Partially correct 7 ms 340 KB Partially correct
15 Partially correct 7 ms 340 KB Partially correct
16 Partially correct 7 ms 340 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 340 KB Partially correct
20 Partially correct 7 ms 340 KB Partially correct
21 Partially correct 7 ms 340 KB Partially correct
22 Partially correct 8 ms 340 KB Partially correct
23 Partially correct 6 ms 340 KB Partially correct
24 Partially correct 7 ms 340 KB Partially correct
25 Partially correct 7 ms 340 KB Partially correct
26 Partially correct 6 ms 340 KB Partially correct
27 Partially correct 7 ms 340 KB Partially correct
28 Partially correct 7 ms 340 KB Partially correct
29 Partially correct 7 ms 340 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 368 KB Partially correct
33 Partially correct 7 ms 340 KB Partially correct
34 Partially correct 8 ms 340 KB Partially correct
35 Partially correct 8 ms 372 KB Partially correct
36 Partially correct 1 ms 212 KB Partially correct