Submission #288171

#	Time	Username	Problem	Language	Result	Execution time	Memory
288171		errorgorn	Xoractive (IZhO19_xoractive)	C++14	100 / 100	9 ms	664 KiB

Xoractive

#include "interactive.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

int val;

set<int> get(vector<int> v){
	multiset<int> res;
	
	v.push_back(1);
	for (auto &it:get_pairwise_xor(v)) res.insert(it);
	
	v.pop_back();
	for (auto &it:get_pairwise_xor(v)) res.erase(res.find(it));
	
	res.erase(0);
	
	set<int> ans;
	for (auto &it:res) ans.insert(it^val);
	
	return ans;
}

struct dat{
	int l,r;
	vector<int> v;
	
	dat(int _l,int _r){
		l=_l,r=_r;
	}
};

vector<dat> v[2];

vector<int> guess(int n) {
	val=ask(1);
	
	v[0].push_back(dat(2,n));
	
	int a=0,b=1;
	
	while (true){
		vector<int> temp;
		bool bad=false;
		
		for (auto &it:v[a]){
			rep(x,it.l,(it.l+it.r)/2+1) temp.push_back(x);
			if (it.l!=it.r || it.v.empty()) bad=true;
		}
		
		if (!bad) break;
		
		auto res=get(temp);
		
		v[b].clear();
		for (auto &it:v[a]){
			if (it.v.empty()){
				dat l=dat(it.l,(it.l+it.r)/2),r=dat((it.l+it.r)/2+1,it.r);
				
				for (auto &it2:res){
					l.v.push_back(it2);
				}
				v[b].push_back(l);
				if (it.l!=it.r) v[b].push_back(r);
			}
			else{
				dat l=dat(it.l,(it.l+it.r)/2),r=dat((it.l+it.r)/2+1,it.r);
				
				for (auto &it2:it.v){
					if (res.count(it2)){
						l.v.push_back(it2);
						res.erase(it2);			
					}
					else r.v.push_back(it2);
				}
				v[b].push_back(l);
				if (it.l!=it.r) v[b].push_back(r);
			}
		}
		swap(a,b);
		
		//for (auto &it:v[a]) cout<<it.r-it.l+1<<" "; cout<<endl;
	}
	
	vector<int> ans={val};
	for (auto &it:v[a]) ans.push_back(it.v[0]);
	
	return ans;
}

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