Submission #503072

#	Time	Username	Problem	Language	Result	Execution time	Memory
503072		Mazaalai	Xoractive (IZhO19_xoractive)	C++17	100 / 100	6 ms	344 KiB

Xoractive

#include "interactive.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define LINE "------------------\n"
#define ALL(x) x.begin(),x.end()
#define print(x) for(auto&el:x)cout<<el<<' ';cout<<'\n';
using namespace std;
using VI = vector <int>;
const int N = 105;
vector <int> ans;
int a1, n, answered;
// get_pairwise_xor, ask
void assign(int pos, int val) {
	answered++;
	ans[pos]=val;
}
VI dif(VI&a, VI&b) {
	VI c;
	int i = 0, j = 0, x = a.size(), y = b.size();
	while(i < x) {
		if (j < y && a[i] == b[j]) {
			i++, j++;
			continue;
		}
		c.pb(a[i++]);
	}
	// cout << "a: ";print(a);
	// cout << "b: ";print(b);
	// cout << "c: ";print(c);
	return c;
}
VI getVals(VI ids) {
	VI ids1 = ids, ret;
	ids.pb(1);
	VI res = get_pairwise_xor(ids);
	VI res1 = get_pairwise_xor(ids1);
	// cout << "res:";print(res);
	// cout << "res1:";print(res1);
	VI vals = dif(res, res1);
	for (int i = 1; i < vals.size(); i+=2) ret.pb(vals[i]^a1);
	// cout << "ids:";print(ids);
	// cout << "ret:";print(ret);
	return ret;
}
VI Union(VI&a, VI&b) {
	set <int> vals(ALL(a));
	for (auto& el : b) vals.insert(el);
	return VI(ALL(vals));
}
VI intersect(VI a, VI b) {
	set <int> vals(ALL(a)), res;
	for (auto& el : b) 
		if (vals.count(el)) res.insert(el);
	return VI(ALL(res));
}
vector<int> guess(int _n) {
	n = _n;
	a1 = ask(1); 
	ans.resize(n);
	assign(0, a1); // 0
	VI ids[10], vals[10];
	for (int i = 2; i <= n; i++) 
	for (int j = 0; (1<<j) <= i; j++) 
		if (i&(1<<j)) ids[j].pb(i);
	// for (int i = 0; i < 10; i++) cout << ids[i].size() << '\n';
	for (int i = 0; !ids[i].empty(); i++) 
		vals[i] = getVals(ids[i]);
	
	VI allVals;
	for (int j = 0; j < 10; j++) sort(ALL(vals[j]));
	for (int i = 0; i < 10; i++)
		allVals = Union(allVals, vals[i]);

	// for (int j = 0; (1<<j) <= n; j++) {
		// cout << j << ": ";
		// print(vals[j]);
	// }
	for (int i = 2; i <= n; i++) {
		VI cur = allVals;
		// cout << LINE;
		// cout << "val: " << i << "\n";
		for (int j = 0; (1<<j) <= n; j++) {
			// cout << j << ": ";
			VI tmp;
			if (i&(1<<j)) {
				// cout << 1 << " ";
				tmp = vals[j];
			} else {
				// cout << 0 << " ";
				tmp = dif(allVals, vals[j]);
			}
			// print(tmp);
			cur = intersect(cur, tmp);
		}
		if (cur.size() != 1) { // error
			ans[0] = -1;
			return ans;
		}
		assign(i-1, cur[0]);
	}
	return ans;
}

Compilation message (stderr)

Xoractive.cpp: In function 'VI getVals(VI)':
Xoractive.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for (int i = 1; i < vals.size(); i+=2) ret.pb(vals[i]^a1);
      |                  ~~^~~~~~~~~~~~~

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