oj.uz

답안 #828319

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
828319 2023-08-17T08:21:04 Z 반딧불(#10380) Toxic Gene (NOI23_toxic) C++17
29.9529 / 100
 5 ms 376 KB 
#include "toxic.h"
#include <bits/stdc++.h>

using namespace std;

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

vector<int> toxicVec, elseVec;
int ans[302]; /// 0: toxic, 1: regular, 2: strong
char chr[] = "TRS";

int queryRange(int l, int r){
	vector<int> v;
	for(int i=l; i<=r; i++) v.push_back(i);
	return query_sample(v);
}

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

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

	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_sample(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(i, chr[ans[i]]);
}

Subtask #1
29.95294118 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Partially correct 4 ms 340 KB Partially correct
3 Partially correct 4 ms 340 KB Partially correct
4 Partially correct 4 ms 340 KB Partially correct
5 Partially correct 4 ms 372 KB Partially correct
6 Partially correct 4 ms 340 KB Partially correct
7 Partially correct 4 ms 360 KB Partially correct
8 Partially correct 4 ms 340 KB Partially correct
9 Partially correct 4 ms 340 KB Partially correct
10 Partially correct 4 ms 364 KB Partially correct
11 Partially correct 4 ms 368 KB Partially correct
12 Partially correct 4 ms 340 KB Partially correct
13 Partially correct 4 ms 372 KB Partially correct
14 Partially correct 4 ms 376 KB Partially correct
15 Partially correct 4 ms 340 KB Partially correct
16 Partially correct 4 ms 372 KB Partially correct
17 Partially correct 4 ms 372 KB Partially correct
18 Partially correct 4 ms 340 KB Partially correct
19 Partially correct 4 ms 340 KB Partially correct
20 Partially correct 5 ms 372 KB Partially correct
21 Partially correct 4 ms 340 KB Partially correct
22 Partially correct 4 ms 340 KB Partially correct
23 Partially correct 4 ms 340 KB Partially correct
24 Correct 4 ms 340 KB Output is correct
25 Correct 4 ms 340 KB Output is correct
26 Correct 4 ms 340 KB Output is correct
27 Correct 4 ms 340 KB Output is correct
28 Correct 4 ms 340 KB Output is correct
29 Correct 5 ms 340 KB Output is correct
30 Correct 5 ms 340 KB Output is correct
31 Correct 4 ms 340 KB Output is correct
32 Correct 4 ms 340 KB Output is correct
33 Correct 4 ms 340 KB Output is correct
34 Partially correct 4 ms 340 KB Partially correct
35 Partially correct 4 ms 340 KB Partially correct
36 Partially correct 1 ms 212 KB Partially correct