oj.uz

답안 #941049

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
941049 2024-03-08T05:53:48 Z daoquanglinh2007 Toxic Gene (NOI23_toxic) C++17
9.46154 / 100
 7 ms 600 KB 
#include <bits/stdc++.h>
#include "toxic.h"
using namespace std;

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

const int NM = 300;

int n;
char a[NM+5];

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

bool calc(){
	int cnt = 0;
	for (int i = 1; i <= n; i++)
		if (a[i] == '?') cnt++;
	return cnt;
}

void determine_type(int _n){
	int n = _n;
	for (int i = 1; i <= n; i++) a[i] = '?';
	while (true){
		int cnt = calc();
		if (cnt <= 60) break;
		vector <int> arr = {}, species;
		for (int i = 1; i <= n; i++)
			if (a[i] == '?') arr.push_back(i);
		shuffle(arr.begin(), arr.end(), rng);
		int sz = (cnt+29)/30;
		for (int i = 0; i < isz(arr); i += sz){
			species.clear();
			for (int j = i; j < min(i+sz, isz(arr)); j++)
				species.push_back(j);
			if (query_sample(species) == isz(species)){
				for (int x : species) a[x] = '!';
			}
		}	
	}
	int ft = -1;
	for (int i = 1; i <= n; i++)
		if (a[i] == '?'){
			if (query_sample({i}) > 0) a[i] = '!'; else a[i] = 'T';
			if (ft == -1 && a[i] == 'T') ft = i;
		}
	while (true){
		vector <int> arr = {};
		for (int i = 1; i <= n; i++)
			if (a[i] == '!' && isz(arr) < 8) arr.push_back(i);
		if (arr.empty()) break;
		vector <int> species = {};
		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
9.46153846 / 100.0

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