Submission #649732

#	Time	Username	Problem	Language	Result	Execution time	Memory
649732		ymm	Xoractive (IZhO19_xoractive)	C++17	100 / 100	3 ms	344 KiB

Xoractive

#include "interactive.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

vector<int> guess(int n)
{
	int val0 = ask(1);
	vector<vector<int>> vec;
	for (int b = 1; b < n; b *= 2) {
		vector<int> v, v0{1}, dif;
		Loop (i,0,n) {
			if (i&b) {
				v.push_back(i+1);
				v0.push_back(i+1);
			}
		}
		v = get_pairwise_xor(v);
		v0 = get_pairwise_xor(v0);
		set_difference(v0.begin(), v0.end(),
		               v.begin(), v.end(),
		               back_inserter(dif));
		vector<int> u;
		for (int i = 1; i < dif.size(); i += 2)
			u.push_back(dif[i] ^ val0);
		sort(u.begin(), u.end());
		vec.push_back(u);
	}
	vector<int> ans{val0};
	Loop (i,1,n) {
		int b = __builtin_ctz(i);
		vector<int> v = vec[b];
		Loop (j,0,b) {
			vector<int> tmp;
			set_difference(v.begin(), v.end(),
			               vec[j].begin(), vec[j].end(),
			               back_inserter(tmp));
			v = tmp;
		}
		Loop (j,b+1,vec.size()) {
			if (i&(1<<j)) {
				vector<int> tmp;
				set_intersection(
					v.begin(), v.end(),
					vec[j].begin(), vec[j].end(),
					back_inserter(tmp));
				v = tmp;
			} else {
				vector<int> tmp;
				set_difference(v.begin(), v.end(),
					       vec[j].begin(), vec[j].end(),
					       back_inserter(tmp));
				v = tmp;
			}
		}
		assert(v.size() == 1);
		ans.push_back(v[0]);
	}
	return ans;
}

Compilation message (stderr)

Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:28:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for (int i = 1; i < dif.size(); i += 2)
      |                   ~~^~~~~~~~~~~~

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