제출 #288156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288156		errorgorn	Xoractive (IZhO19_xoractive)	C++14	88 / 100	11 ms	896 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);
	
	vector<int> temp;
	rep(x,2,n+1){
		temp.push_back(x);
	}
	
	v[0].push_back(dat(2,n));
	for (auto &it:get(temp)) v[0].back().v.push_back(it);
	
	int a=0,b=1;
	
	while (true){
		temp.clear();
		
		for (auto &it:v[a]){
			rep(x,it.l,(it.l+it.r+1)/2) temp.push_back(x);
		}
		
		if (temp.empty()) break;
		
		auto res=get(temp);
		
		v[b].clear();
		for (auto &it:v[a]){
			if (it.l==it.r) v[b].push_back(it);
			else{
				dat l=dat(it.l,(it.l+it.r+1)/2-1),r=dat((it.l+it.r+1)/2,it.r);
				
				for (auto &it2:it.v){
					if (res.count(it2)) l.v.push_back(it2);
					else r.v.push_back(it2);
				}
				v[b].push_back(l);
				v[b].push_back(r);
			}
		}
		swap(a,b);
	}
	
	vector<int> ans={val};
	for (auto &it:v[a]) ans.push_back(it.v[0]);
	
	return ans;
}

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