Submission #1161341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161341		MisterReaper	Xoractive (IZhO19_xoractive)	C++20	100 / 100	2 ms	480 KiB

Xoractive

#include "interactive.h"
#include "bits/stdc++.h"

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

// vector<int> guess(int n) {
// 	vector <int> ans;
// 	for (int i = 1; i <= n; i++) {
// 		ans.push_back(ask(i));
// 	}
// 	return ans;
// }

std::vector<int> xor_vectors(std::vector<int> a, std::vector<int> b) {
	std::sort(a.begin(), a.end());
	std::sort(b.begin(), b.end());

	std::vector<int> ans;
	int na = a.size(), nb = b.size();
	int pa = 0, pb = 0;
	while (pa < na && pb < nb) {
		if (a[pa] == b[pb]) {
			pa++, pb++;
		} else if (a[pa] < b[pb]) {
			ans.emplace_back(a[pa++]);
		} else {
			ans.emplace_back(b[pb++]);
		}
	}
	while (pa < na) {
		ans.emplace_back(a[pa++]);
	}
	while (pb < nb) {
		ans.emplace_back(b[pb++]);
	}
	return ans;
}

std::vector<int> union_vectors(std::vector<int> a, std::vector<int> b) {
	std::sort(a.begin(), a.end());
	std::sort(b.begin(), b.end());

	std::vector<int> ans;
	int na = a.size(), nb = b.size();
	int pa = 0, pb = 0;
	while (pa < na && pb < nb) {
		if (a[pa] == b[pb]) {
			ans.emplace_back(a[pa]);
			pa++, pb++;
		} else if (a[pa] < b[pb]) {
			ans.emplace_back(a[pa++]);
		} else {
			ans.emplace_back(b[pb++]);
		}
	}
	while (pa < na) {
		ans.emplace_back(a[pa++]);
	}
	while (pb < nb) {
		ans.emplace_back(b[pb++]);
	}
	return ans;
}

std::vector<int> cross_vectors(std::vector<int> a, std::vector<int> b) {
	std::sort(a.begin(), a.end());
	std::sort(b.begin(), b.end());

	std::vector<int> ans;
	int na = a.size(), nb = b.size();
	int pa = 0, pb = 0;
	while (pa < na && pb < nb) {
		if (a[pa] == b[pb]) {
			ans.emplace_back(a[pa]);
			pa++, pb++;
		} else if (a[pa] < b[pb]) {
			pa++;
		} else {
			pb++;
		}
	}
	while (pa < na) {
		pa++;
	}
	while (pb < nb) {
		pb++;
	}
	return ans;
}

std::vector<int> simplify(std::vector<int> x) {
	int nx = int(x.size());
	assert(nx % 2 == 0);

	std::vector<int> ans;
	for (int i = 0; i < nx; i += 2) {
		assert(x[i] == x[i + 1]);
		ans.emplace_back(x[i]);
	}
	return ans;
}

std::vector<int> guess(int N) {
	std::vector<int> ans;
	
	int x = ask(1);
	ans.emplace_back(x);

	auto extract = [&x](std::vector<int> v) -> std::vector<int> {
		if (v.empty()) {
			return {};
		}
		auto v1 = get_pairwise_xor(v);
		v.emplace_back(1);
		auto v2 = get_pairwise_xor(v);
		auto ans = xor_vectors(v1, v2);
		ans.erase(std::find(ans.begin(), ans.end(), 0));
		ans = simplify(ans);
		return ans;
	};
	
	std::vector<std::vector<int>> v(7);
	for (int i = 1; i < N; ++i) {
		for (int j = 0; j < 7; ++j) {
			if (i >> j & 1) {
				v[j].emplace_back(i + 1);
			}
		}
	}

	std::vector<std::vector<int>> xrs(7);
	for (int i = 0; i < 7; ++i) {
		xrs[i] = extract(v[i]);
		debug(i, xrs[i]);
	}

	std::vector<int> all;
	for (int i = 0; i < 7; ++i) {
		all = union_vectors(all, xrs[i]);
	}

	for (int i = 1; i < N; ++i) {
		std::vector<int> vec = all;
		for (int j = 0; j < 7; ++j) {
			if (xrs[j].empty()) {
				continue;
			}
			if (i >> j & 1) {
				vec = cross_vectors(vec, xrs[j]);
			} else {
				vec = cross_vectors(vec, xor_vectors(all, xrs[j]));
			}
		}
		debug(i, vec);
		assert(vec.size() == 1);
		ans.emplace_back(vec[0] ^ x);
	}

	debug(ans);

	return ans;
}

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