Submission #337772

#	Time	Username	Problem	Language	Result	Execution time	Memory
337772		tengiz05	Xoractive (IZhO19_xoractive)	C++17	0 / 100	9 ms	1644 KiB

Xoractive

#include "interactive.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int msb(int val){return sizeof(int)*8-__builtin_clz(val)-1;}
vector<int> guess(int n) {
	vector <int> ans(n);
	vector<multiset<int>> v(8);
	vector<multiset<int>> o(8);
	ans[0] = ask(1);
	for(int j=0;j<7;j++){
		vector<int> todo;
		for(int i=2;i<=n;i++){
			if(i&(1<<j))todo.pb(i);
		}if(todo.empty())continue;
		vector<int> tmp = get_pairwise_xor(todo);
		for(auto x : tmp){
			v[j].insert(x);
		}todo.pb(1);
		tmp = get_pairwise_xor(todo);
		for(auto x : tmp){
			o[j].insert(x);
		}
	}

	for(int i=0;i<7;i++){
		for(auto x : v[i]){
			o[i].erase(o[i].find(x));
		}
	}
	for(int i=2;i<=n;i++){
		multiset<int> res;
		for(auto x : o[msb(i)])res.insert(x);
		for(int j=0;j<7;j++){
			if(i&(1<<j)){
			}else {
				for(auto x : o[j]){
					if(res.find(x) != res.end())res.erase(res.find(x));
				}
			}
		}
		assert(res.size());
		ans[i-1] = (*res.rbegin())^ans[0];
	}
	return ans;
}

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