Submission #1205999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205999		dosts	Xoractive (IZhO19_xoractive)	C++20	88 / 100	5 ms	784 KiB

Xoractive

#include "interactive.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;
using namespace std;

int x;
vi difference(vi v1,vi v2) {
	multiset<int> ms;
	for (auto it : v2) ms.insert(it);
	for (auto it : v1) ms.erase(ms.find(it));
	return vi(all(ms));
}

vi isect(vi v1,vi v2) {
	multiset<int> ms;
	for (auto it : v1) ms.insert(it);
	vi ret;
	for (auto it : v2) {
		if (ms.find(it) != ms.end()) ret.push_back(it),ms.erase(ms.find(it));
	}
	return ret;
}

vi figureout(vi v1,vi v2) {
	vi nw = difference(v1,v2);
	for (auto& it : nw) it^=x;
	return nw;
}

vi getxors(vi v) {
	if (v.empty()) return {};
	vi vv = get_pairwise_xor(v);
	reverse(all(vv));
	while (!vv.empty() && vv.back() == 0) vv.pop_back();
	reverse(all(vv));
	vi vvv;
	for (int i = 0;i<vv.size();i+=2) vvv.push_back(vv[i]);
	return vvv;
}

vector<int> guess(int n) {
	vi ans(n);
	x = ans[0] = ask(1);
	vi elems[7][2];
	vi init;
	for (int i=2;i<=n;i++) init.push_back(i);
	vi vv1 = getxors(init);
	init.push_back(1);
	vi vv2 = getxors(init);
	vi todos = figureout(vv1,vv2);

	for (int i = 0;i<7;i++) {
		vi toask;
		for (int j=1;j<n;j++) {
			if ((j-1)&(1<<i)) toask.push_back(j+1);
		}
		vi v1 = getxors(toask);
		toask.push_back(1);
		vi v2 = getxors(toask);
		vi here = figureout(v1,v2);
		elems[i][1] = here;
		elems[i][0] = difference(here,todos);
	}
	for (int i=1;i<n;i++) {
		vi cur = todos;
		for (int j = 0;j<7;j++) {
			if ((i-1)&(1<<j)) cur = isect(cur,elems[j][1]);
			else cur = isect(cur,elems[j][0]);
		}
		ans[i] = cur.back();
	}
	return ans;
}

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