Submission #469556

#	Time	Username	Problem	Language	Result	Execution time	Memory
469556		keta_tsimakuridze	Xoractive (IZhO19_xoractive)	C++14	100 / 100	9 ms	636 KiB

Xoractive

#include<bits/stdc++.h>
#include "interactive.h"
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t,n,a[N];
map<int,int> ind;
/*
int ask(int x) {
	return a[x];
}
vector<int> get_pairwise_xor(vector<int> v){
	vector<int> x;
	for(int j = 0; j < v.size(); j++) {
		for(int i = 0; i < v.size(); i++) {
			x.push_back(a[v[i]] ^ a[v[j]]);
		}
	}
	return x;
}
*/
multiset<int> get(vector<int> x) {
	multiset<int> s;
	for(int i = 0; i < x.size(); i++) s.insert(x[i]);
	return s;
}

vector<int> guess(int n) {
	vector<int> ans(n);
	ans[0] = ask(1);
	set<int> s;	
	for(int i = 0; (1 << i) < n; i++){
		vector<int> x;
		for(int j = 1; j < n; j++) {
			if((1 << i) & j) x.push_back(j + 1);
		}
		x.push_back(1);
		vector<int> g = get_pairwise_xor(x);
		multiset<int> s1 = get(g);
		x.pop_back();
		g = get_pairwise_xor(x);
		multiset<int> s2 = get(g);
		for(multiset<int> :: iterator it = s2.begin(); it != s2.end(); it++) {
			s1.erase(s1.find(*it));
		}
		s1.erase(0);
		while(s1.size()) {
			int x = *s1.begin();
			ind[x] += 1 << i;
			s1.erase(x);
			s.insert(x);
		}
	}

	for(set<int> :: iterator it = s.begin(); it != s.end(); it++) {
		ans[ind[*it]] = (*it) ^ ans[0];
	}
	return ans;
}
/*
main(){
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	vector<int> ans = guess(n);
	for(int j = 0; j < n; j++) cout << ans[j] <<" ";
}
*/

Compilation message (stderr)

Xoractive.cpp: In function 'std::multiset<int> get(std::vector<int>)':
Xoractive.cpp:26:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i = 0; i < x.size(); i++) s.insert(x[i]);
      |                 ~~^~~~~~~~~~

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