Submission #1147341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147341		Pacybwoah	Toxic Gene (NOI23_toxic)	C++20	67.60 / 100	13 ms	492 KiB

toxic

#include "toxic.h"
#include<vector>
#include<algorithm>
#include<iostream>
#include<chrono>
#include<random>
using namespace std;
const int k = 8;
void determine_type(int n){
	auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
	mt19937_64 mt(seed);
	vector<int> vec(n), ans(n + 1, -1), good;
	for(int i = 0; i < n; i++) vec[i] = i + 1;
	shuffle(vec.begin(), vec.end(), mt);
	int tox;
	while(!vec.empty()){
		int sz = min((int)vec.size(), k);
		vector<int> ask;
		for(int i = 0; i < sz; i++){
			for(int j = 0; j < (1 << i); j++) ask.push_back(vec[i]);
		}
		int res = query_sample(ask);
		if(res == (int)ask.size()){
			for(int i = 0; i < sz; i++) good.push_back(vec[i]);
			for(int i = 0; i < sz; i++) vec.erase(vec.begin());
			continue;
		}
		vector<int> cur;
		for(int i = sz - 1; i >= 0; i--){
			if((1 << i) & res){
				ans[vec[i]] = 1;
				vec.erase(vec.begin() + i);
			}
			else{
				cur.push_back(vec[i]);
			}
		}
		reverse(cur.begin(), cur.end());
		sz = (int)cur.size();
		int l = 0, r = sz - 1;
		while(l < r){
			vector<int>().swap(ask);
			int mid = (l + r) >> 1;
			for(int i = 0; i <= mid; i++) ask.push_back(cur[i]);
			if(query_sample(ask) > 0) l = mid + 1;
			else r = mid;
		}
		for(int i = 0; i < l; i++) ans[cur[i]] = 0;
		ans[cur[l]] = 2;
		tox = cur[l];
		for(int i = 0; i <= l; i++) vec.erase(vec.begin());
	}
	while(!good.empty()){
		int sz = min((int)good.size(), 8);
		vector<int> ask;
		for(int i = 0; i < sz; i++){
			for(int j = 0; j < (1 << i); j++) ask.push_back(good[i]);
		}
		ask.push_back(tox);
		int res = query_sample(ask);
		for(int i = 0; i < sz; i++){
			if(res & (1 << i)) ans[good[i]] = 1;
			else ans[good[i]] = 0;
		}
		for(int i = 0; i < sz; i++) good.erase(good.begin());
	}
	//for(int i = 1; i <= n; i++) cout << ans[i] << " ";
	for(int i = 1; i <= n; i++) answer_type(i, char('R' + ans[i]));
}
// g++ -std=c++20 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run toxic.cpp stub.cpp

• Subtask 1: 67.6 / 100