oj.uz

답안 #942317

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
942317 2024-03-10T12:45:21 Z daoquanglinh2007 Toxic Gene (NOI23_toxic) C++17
58.15 / 100
 8 ms 604 KB 
#include <bits/stdc++.h>
#include "toxic.h"
using namespace std;

#define isz(a) (int)(a).size()

const int NM = 300;

int p[NM+5];
char a[NM+5];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void determine_type(int n){
	for (int i = 1; i <= n; i++){
		a[i] = ' ';
		p[i] = i;
	}
	shuffle(p+1, p+1+n, rng);
	int cur = 0, ft = -1;
	while (cur < n){
		int l = cur+1, r = min(n, cur+8);
		vector <int> species = {};
		for (int i = cur+1; i <= r; i++)
			species.push_back(p[i]);
		if (query_sample(species) == r-cur){
			cur = r;
			continue;
		}
		r--;
		int res = r+1;
		while (l <= r){
			int mid = (l+r)/2;
			species.clear();
			for (int i = cur+1; i <= mid; i++)
				species.push_back(p[i]);
			if (query_sample(species) < mid-cur){
				res = mid;
				r = mid-1;
			}
			else l = mid+1;
		}
		a[p[res]] = 'T';
		cur = res;
		if (ft == -1) ft = p[res];
	}
	while (true){
		vector <int> arr = {}, species = {};
		for (int i = 1; i <= n; i++){
			if (a[i] == ' ' && isz(arr) < 8) arr.push_back(i); 
		}
		if (arr.empty()) break;
		for (int i = 0; i < isz(arr); i++){
			for (int j = 0; j < (1<<i); j++) species.push_back(arr[i]);
		}
		species.push_back(ft);
		int tmp = query_sample(species);
		for (int i = 0; i < isz(arr); i++)
			if ((tmp>>i)&1) a[arr[i]] = 'S'; else a[arr[i]] = 'R';
	}
	for (int i = 1; i <= n; i++)
		answer_type(i, a[i]);
}

Subtask #1
58.15 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Partially correct 8 ms 540 KB Partially correct
3 Partially correct 6 ms 348 KB Partially correct
4 Partially correct 6 ms 520 KB Partially correct
5 Partially correct 6 ms 348 KB Partially correct
6 Partially correct 6 ms 600 KB Partially correct
7 Partially correct 6 ms 348 KB Partially correct
8 Partially correct 6 ms 600 KB Partially correct
9 Partially correct 6 ms 344 KB Partially correct
10 Partially correct 6 ms 348 KB Partially correct
11 Partially correct 6 ms 540 KB Partially correct
12 Partially correct 6 ms 348 KB Partially correct
13 Partially correct 6 ms 536 KB Partially correct
14 Partially correct 6 ms 344 KB Partially correct
15 Partially correct 6 ms 604 KB Partially correct
16 Partially correct 6 ms 540 KB Partially correct
17 Partially correct 6 ms 348 KB Partially correct
18 Partially correct 6 ms 540 KB Partially correct
19 Partially correct 6 ms 348 KB Partially correct
20 Partially correct 6 ms 344 KB Partially correct
21 Partially correct 6 ms 348 KB Partially correct
22 Partially correct 6 ms 456 KB Partially correct
23 Partially correct 6 ms 456 KB Partially correct
24 Partially correct 5 ms 344 KB Partially correct
25 Partially correct 7 ms 540 KB Partially correct
26 Partially correct 5 ms 516 KB Partially correct
27 Partially correct 5 ms 348 KB Partially correct
28 Partially correct 5 ms 344 KB Partially correct
29 Partially correct 5 ms 348 KB Partially correct
30 Partially correct 5 ms 348 KB Partially correct
31 Partially correct 6 ms 348 KB Partially correct
32 Partially correct 6 ms 348 KB Partially correct
33 Partially correct 5 ms 516 KB Partially correct
34 Partially correct 6 ms 344 KB Partially correct
35 Partially correct 7 ms 348 KB Partially correct
36 Partially correct 1 ms 348 KB Partially correct