Submission #1206025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206025		dosts	Xoractive (IZhO19_xoractive)	C++20	100 / 100	4 ms	572 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 = 1e7+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 combine(vi v1,vi v2) {
	for (auto it : v2) v1.push_back(it);
	sort(all(v1));
	v1.erase(unique(all(v1)),v1.end());
	return v1;
}

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];
	for (int i = 0;i<7;i++) {
		vi toask;
		for (int j=1;j<n;j++) {
			if ((j-1)&(1<<i)) ;
			else toask.push_back(j+1);
		}
		vi v1 = getxors(toask);
		toask.push_back(1);
		vi v2 = getxors(toask);
		vi here = figureout(v1,v2);
		elems[i][0] = here;
	}
	vi todos;
	for (int i = 0;i<7;i++) todos = combine(todos,elems[i][0]);
	for (int i = 0;i<7;i++) elems[i][1] = difference(elems[i][0],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: 94 / 94