Submission #503474

#	Time	Username	Problem	Language	Result	Execution time	Memory
503474		Gurban	Xoractive (IZhO19_xoractive)	C++17	88 / 100	8 ms	912 KiB

Xoractive

#include "bits/stdc++.h"
#include "interactive.h"
using namespace std;

const int maxn=105;
int a[maxn];
int lft[4*maxn],rgt[4*maxn];
set<int>arr[4*maxn];
vector<int>fn;
map<int,vector<int>>m;

void f(int l,int r,int nd,int lev){
	lft[nd] = l;
	rgt[nd] = r;
	m[lev].push_back(nd);
	if(l == r){
		fn.push_back(nd);
		return;
	}
	int md = (l + r) / 2;
	f(l,md,nd*2,lev+1);
	f(md+1,r,nd*2+1,lev+1);
}

set<int>A(vector<int>v){
	if(v.empty()) return set<int>();
	
	// for(auto i : v) cout<<i<<' ';
	// cout<<" ----> ";

	vector<int>now = v;
	now.push_back(1);

	vector<int>nw = get_pairwise_xor(now);
	vector<int>z = get_pairwise_xor(v);

	// for(auto i : nw) cout<<i<<' ';
	// cout<<" ----> ";
	// for(auto i : z) cout<<i<<' ';
	// cout<<" ----> ";

	multiset<int>SS(nw.begin(),nw.end());
	for(auto i : z) SS.erase(SS.find(i));

	// for(auto i : SS) cout<<i<<' ';
	// cout<<" ---> ";

	set<int>jg;
	for(auto i : SS) jg.insert(i ^ a[1]);
	jg.erase(a[1]);
	
	// for(auto i : jg) cout<<i<<' ';
	// cout<<'\n';

	return jg;
}

vector<int> guess(int n) {
	a[1] = ask(1);
	f(2,n,1,1);
	vector<int>go;
	for(int i = 2;i <= n;i++) go.push_back(i);
	arr[1] = A(go);
	for(auto i : m){
		if(i.first == 1) continue;
		vector<int>now;
		for(auto j : i.second){
			if(!(j & 1)) for(int k = lft[j];k <= rgt[j];k++){
				now.push_back(k);
			}
		}
		set<int>sw = A(now);
		for(auto j : i.second){
			if(j & 1){
				arr[j] = arr[(j-1)/2];
				for(auto l : arr[j-1]) arr[j].erase(l);
			}
			else {
				for(auto l : arr[j/2]) if(sw.find(l) != sw.end()) arr[j].insert(l);
			}
		}
	}
	// for(int i = 1;i <= 2*n;i++){
	// 	cout<<i<<' '<<lft[i]<<' '<<rgt[i]<<" ----> ";
	// 	for(auto j : arr[i]) cout<<j<<' ';
	// 	cout<<'\n';
	// }
	vector<int>ans; ans.push_back(a[1]);
	for(auto i : fn){
		if(!arr[i].empty()) ans.push_back(*arr[i].begin());
	}
	return ans;
}

• Subtask 1: 6 / 6
• Subtask 2: 82 / 94