oj.uz

답안 #828284

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
828284 2023-08-17T07:45:03 Z 박상훈(#10381) Toxic Gene (NOI23_toxic) C++17
63.55 / 100
 11 ms 516 KB 
#include "toxic.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int I[303];
mt19937 seed(1557);

pair<vector<int>, vector<int>> query_exp(const vector<int> &V, const vector<int> &W){
	vector<int> Q;
	for (int i=0;i<(int)V.size();i++){
		for (int j=0;j<(1<<i);j++) Q.push_back(V[i]);
	}

	for (int i=0;i<(int)W.size();i++) Q.push_back(W[i]);

	for (auto &x:Q) x = I[x];
	int ret = query_sample(Q);
	vector<int> dead, alive;

	for (int i=0;i<(int)V.size();i++){
		if (ret&(1<<i)) alive.push_back(V[i]);
		else dead.push_back(V[i]);
	}

	return {dead, alive};
}

int query_linear(const vector<int> &V){
	vector<int> Q;
	for (auto &x:V) Q.push_back(I[x]);
	return query_sample(Q);
}

int search(const vector<int> &dead){
	int l = 0, r = (int)dead.size()-1;
	while(l<r){
		int m = (l+r)>>1;
		vector<int> V;
		for (int i=l;i<=m;i++) V.push_back(dead[i]);

		if (query_linear(V)==(int)V.size()) l = m+1;
		else r = m;
	}

	return dead[l];
}

void determine_type(int n){
	for (int i=1;i<=n;i++) I[i] = i;
	shuffle(I+1, I+n+1, seed);
	
	vector<char> typ(n+1);
	vector<int> toxic;
	vector<pair<int, int>> P;

	for (int i=1;i<=n;i+=8){
		int r = min(n, i+7);

		vector<int> V;
		for (int j=i;j<=r;j++) V.push_back(j);
		
		auto [dead, alive] = query_exp(V, vector<int>());
		if (dead.empty()){P.emplace_back(i, r); continue;}

		for (auto &x:alive) typ[x] = 'S';

		// printf("dead: ");
		// for (auto &x:dead) printf("%d ", x);
		// printf("\n");

		// printf("alive: ");
		// for (auto &x:alive) printf("%d ", x);
		// printf("\n");
		
		while(true){
			int p = search(dead);
			toxic.push_back(p);
			typ[p] = 'T';

			// printf("found toxic: %d\n", I[p]);

			dead.erase(find(dead.begin(), dead.end(), p));
			if (query_linear(dead)==(int)dead.size()) break;
		}

		for (auto &x:dead) typ[x] = 'R';
	}

	for (auto &[l, r]:P){
		vector<int> V;
		for (int j=l;j<=r;j++) V.push_back(j);

		auto [dead, alive] = query_exp(V, vector<int>(1, toxic[0]));
		for (auto &x:dead) typ[x] = 'R';
		for (auto &x:alive) typ[x] = 'S';
	}

	for (int i=1;i<=n;i++) answer_type(I[i], typ[i]);
}

Subtask #1
63.55 / 100.0

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