oj.uz

Submission #828339

# Submission time Handle Problem Language Result Execution time Memory
828339 2023-08-17T08:38:18 Z 박상훈(#10381) Toxic Gene (NOI23_toxic) C++17
62.2 / 100
 11 ms 400 KB 
#include "toxic.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

mt19937 seed(1557);

int I[303], mem;
vector<char> typ;

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);
	mem = (int)Q.size() - ret;
	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, vector<vector<int>> &P){
	int l = 0, r = (int)dead.size()-1;
	while(l<r){
		int m = (l+r)>>1;
		vector<int> V, fuck;
		for (int i=l;i<=m;i++) V.push_back(dead[i]);

		if (!P.empty()){
			fuck = P.back();

			auto [deadF, aliveF] = query_exp(fuck, V);
			if (mem==0) l = m+1;
			else{
				for (auto &x:deadF) typ[x] = 'R';
				for (auto &x:aliveF) typ[x] = 'S';
				P.pop_back();
				r = m;
			}
		}

		else{
			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);
	
	typ.clear();
	typ.resize(n+1);
	vector<int> toxic, que0;
	vector<vector<int>> P, que;

	int B = 8;
	int lim = 8;

	for (int i=1;i<=n;i+=B){
		int r = min(n, i+B-1);

		vector<int> V;
		for (int j=i;j<=r;j++) V.push_back(j);
		
		int val = query_linear(V);
		if (val==(int)V.size()){
			if (P.empty()) P.push_back(vector<int>());
			for (int j=i;j<=r;j++){
				if ((int)P.back().size()==lim) P.push_back(vector<int>());
				P.back().push_back(j);
			}

			continue;
		}

		for (auto &x:V) que0.push_back(x);
		continue;

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

		// que.push_back(dead);
		// continue;

		// 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, P);
		// 	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';
	}

	// printf("ok\n");

	for (int i=0;i<(int)que0.size();i+=lim){
		int r = min((int)que0.size()-1, i+lim-1);

		vector<int> V;
		for (int j=i;j<=r;j++) V.push_back(que0[j]);

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

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

		que.push_back(dead);
		// printf("push: ");
		// for (auto &x:dead) printf("%d ", x);
		// printf("\n");
	}

	// printf("okok\n");

	while(que.size() >= 2){
		auto X = que.back(); que.pop_back();
		auto Y = que.back();

		for (auto &x:Y) X.push_back(x);
		// bool flag = find(X.begin(), X.end(), 240)!=X.end();
		// if (flag){
		// 	for (auto &x:X) printf(" %d", x);
		// 	printf("\n");
		// }

		int p = search(X, P);
		toxic.push_back(p);
		typ[p] = 'T';
		// printf("toxic found %d\n", I[p]);

		auto titer = find(X.begin(), X.end(), p);
		for (auto iter=X.begin();iter!=titer;iter++){
			typ[*iter] = 'R';
		}
		X.erase(X.begin(), next(titer));

		// if (flag){
		// 	for (auto &x:X) printf(" %d", x);
		// 	printf("\n");
		// }

		if (X.size() > Y.size()){
			for (int i=0;i<(int)Y.size();i++) X.pop_back();
			que.push_back(X);
		}

		else{
			que.pop_back();
			que.push_back(X);
		}
	}

	assert(que.size()==1);

	for (auto &dead:que){
		if (query_linear(dead)==(int)dead.size()){
			for (auto &x:dead) typ[x] = 'R';
			continue;
		}

		while(true){
			int p = search(dead, P);
			toxic.push_back(p);
			typ[p] = 'T';

			auto titer = find(dead.begin(), dead.end(), p);
			for (auto iter=dead.begin();iter!=titer;iter++){
				typ[*iter] = 'R';
			}
			dead.erase(dead.begin(), next(titer));

			if (query_linear(dead)==(int)dead.size()) break;
		}

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

	for (auto &V:P){
		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
62.2 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Partially correct 8 ms 384 KB Partially correct
3 Partially correct 8 ms 388 KB Partially correct
4 Partially correct 8 ms 340 KB Partially correct
5 Partially correct 9 ms 340 KB Partially correct
6 Partially correct 9 ms 376 KB Partially correct
7 Partially correct 10 ms 340 KB Partially correct
8 Partially correct 9 ms 340 KB Partially correct
9 Partially correct 9 ms 380 KB Partially correct
10 Partially correct 9 ms 340 KB Partially correct
11 Partially correct 9 ms 380 KB Partially correct
12 Partially correct 9 ms 340 KB Partially correct
13 Partially correct 11 ms 388 KB Partially correct
14 Partially correct 8 ms 384 KB Partially correct
15 Partially correct 9 ms 340 KB Partially correct
16 Partially correct 10 ms 340 KB Partially correct
17 Partially correct 11 ms 400 KB Partially correct
18 Partially correct 9 ms 340 KB Partially correct
19 Partially correct 10 ms 340 KB Partially correct
20 Partially correct 9 ms 340 KB Partially correct
21 Partially correct 9 ms 340 KB Partially correct
22 Correct 7 ms 340 KB Output is correct
23 Correct 6 ms 340 KB Output is correct
24 Partially correct 9 ms 384 KB Partially correct
25 Partially correct 9 ms 384 KB Partially correct
26 Partially correct 9 ms 384 KB Partially correct
27 Partially correct 9 ms 340 KB Partially correct
28 Partially correct 8 ms 340 KB Partially correct
29 Partially correct 9 ms 376 KB Partially correct
30 Partially correct 9 ms 380 KB Partially correct
31 Partially correct 9 ms 376 KB Partially correct
32 Partially correct 10 ms 384 KB Partially correct
33 Partially correct 9 ms 380 KB Partially correct
34 Partially correct 9 ms 340 KB Partially correct
35 Partially correct 9 ms 388 KB Partially correct
36 Partially correct 1 ms 212 KB Partially correct