Submission #288956

#	Time	Username	Problem	Language	Result	Execution time	Memory
288956		AMO5	Xoractive (IZhO19_xoractive)	C++17	100 / 100	40 ms	512 KiB

Xoractive

#include <bits/stdc++.h>
#include "interactive.h"

using namespace std;

#define ii pair<int,int>
#define vi vector<int>
#define sz(x) (int)x.size()

vi pos[111];

vi guess(int n){
	vi res;
	res.resize(n);
	if(n<=15){
		for(int i=0; i<n; i++)
			res[i]=ask(i+1);
		return res;
	}
	res[0]=(ask(1));
	int k=-1;
	while(n>(1<<++k)){}
	for(int i=0; i<k; i++){
		vi po;
		for(int j=0; j<n; j++){
			if(j>>i&1)po.emplace_back(j+1);
		}
		vi q = get_pairwise_xor(po);
		po.emplace_back(1);
		
		pos[i] = get_pairwise_xor(po);
		pos[i].erase(pos[i].begin());
		for(int x:q)
			pos[i].erase(find(pos[i].begin(),pos[i].end(),x));
		for(int &x:pos[i]){
			x=x^res[0];
		}
	}
	for(int i=1; i<n; i++){
		vi v;
		for(int j=0; j<k; j++){
			if((i>>j&1)^1)continue;
			//settle overlapping
			if(sz(v)){
				vi w;
				for(int x:pos[j]){
					if(find(v.begin(),v.end(),x)!=v.end())
						w.emplace_back(x);
				}
				v = w;
			}else{
				v = pos[j];
			}
		}
		for(int j=0; j<k; j++){
			if(i>>j&1)continue;
			for(int x:pos[j]){
				if(find(v.begin(),v.end(),x)!=v.end())
					v.erase(find(v.begin(),v.end(),x));
			}
		}
		res[i]=v[0];
	}
	return res;
}

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