Submission #1189044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189044		peteza	Xoractive (IZhO19_xoractive)	C++20	100 / 100	4 ms	508 KiB

Xoractive

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

int last;
vector<int> realol[8];

vector<int> guess(int n) {
	if(n <= 15) {
		vector <int> ans;
		for (int i = 1; i <= n; i++) {
			ans.push_back(ask(i));
		}
		return ans;
	}
	vector<int> ans(n);
	ans.back() = ask(n);
	for(int k=0;k<7;k++) {
		vector<int> vec;
		for(int i=1;i<n;i++) {
			if(i & (1 << k)) vec.push_back(i);
		}
		if(vec.empty()) continue;
		auto r1 = get_pairwise_xor(vec); reverse(r1.begin(), r1.end());
		while(!r1.empty() && r1.back() == 0) r1.pop_back();
		vec.push_back(n);
		auto r2 = get_pairwise_xor(vec); reverse(r2.begin(), r2.end());
		while(!r2.empty() && r2.back() == 0) r2.pop_back();
		multiset<int> ms; 
		for(int i=0;i<r2.size();i+=2) ms.insert(r2[i]); 
		for(int i=0;i<r1.size();i+=2) {ms.erase(ms.find(r1[i]));}
		realol[k].clear();
		for(auto &e:ms) realol[k].emplace_back(e);
		for(auto &e:realol[k]) e ^= ans.back();
	}
	for(int i=1;i<n;i++) {
		set<int> candidates;
		for(int k=0;k<7;k++) {
			if((i>>k)&1) {
				for(auto &e:realol[k]) candidates.insert(e);
			}
		}
		for(int k=0;k<7;k++) {
			if((i >> k) & 1) {
				set<int> cinter;
				for(auto &e:realol[k]) {
					if(candidates.find(e) != candidates.end()) cinter.insert(e);
				}
				candidates = cinter;
			} else {
				for(auto &e:realol[k]) candidates.erase(e);
			}
		}
		assert(candidates.size() == 1);
		ans[i-1] = *candidates.begin();
	}
	return ans;
}

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