Submission #701233

#	Time	Username	Problem	Language	Result	Execution time	Memory
701233		erekle	Xoractive (IZhO19_xoractive)	C++17	100 / 100	3 ms	384 KiB

Xoractive

#include "interactive.h"
#include <map>

using namespace std;

vector<int> guess(int n) {
	int x = ask(1), maxBit = 0;
	while ((1 << (maxBit+1)) <= n-1) ++maxBit;
	auto getVals = [&x](vector<int> v) {
		vector<int> p = get_pairwise_xor(v);
		v.push_back(1);
		vector<int> q = get_pairwise_xor(v);
		vector<int> vals;
		for (int i = 0, j = 0; j < q.size(); ++j) {
			if (i < p.size() && p[i] == q[j]) ++i;
			else if (q[j]) vals.push_back(q[j] ^ x);
		}
		return vals;
	};

	map<int, int> where; // value to index
	for (int i = 0; i <= maxBit; ++i) {
		vector<int> v;
		for (int j = 2; j <= n; ++j) {
			if ((j-1) & (1 << i)) v.push_back(j);
		}
		vector<int> res = getVals(v);
		for (int y : res) where[y] |= (1 << i);
	}

	vector<int> ans(n); ans[0] = x;
	for (auto [y, i] : where) ans[i] = y;
	return ans;
}

Compilation message (stderr)

Xoractive.cpp: In lambda function:
Xoractive.cpp:14:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for (int i = 0, j = 0; j < q.size(); ++j) {
      |                          ~~^~~~~~~~~~
Xoractive.cpp:15:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |    if (i < p.size() && p[i] == q[j]) ++i;
      |        ~~^~~~~~~~~~

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