Submission #334437

#	Time	Username	Problem	Language	Result	Execution time	Memory
334437		nikatamliani	Xoractive (IZhO19_xoractive)	C++14	100 / 100	7 ms	492 KiB

Xoractive

#include <bits/stdc++.h>
#include "interactive.h"
using namespace std;
 
vector<int> guess(int n) {
	vector <int> ans;
	int x = ask(1);
	ans.push_back(x);
	set<int> all, s[7];
	for(int bit = 0; bit < 7; ++bit) {
		vector<int> to_ask;
		for(int i = 2; i <= n; ++i) {
			if(i >> bit & 1) {
				to_ask.push_back(i);
			}
		}
		if(to_ask.empty()) continue;
		vector<int> xors_without_1 = get_pairwise_xor(to_ask);
		to_ask.push_back(1);
		vector<int> xors_with_1 = get_pairwise_xor(to_ask);
		map<int,int> freq;
		for(int i : xors_without_1) freq[i]++;
		for(int i : xors_with_1) {
			if(freq[i] == 0) {
				s[bit].insert(i);
				all.insert(i);
			} else {
				--freq[i];
			}
		}
	}
	for(int i = 2; i <= n; ++i) {
		for(int val : all) {
			if(!val) continue;
			bool ok = true; 
			for(int bit = 0; bit < 7; ++bit) {
				if(i >> bit & 1) {
					if(s[bit].find(val) == s[bit].end()) {
						ok = false;
					}
				} else {
					if(s[bit].find(val) != s[bit].end()) {
						ok = false;
					}
				}
			}
			if(ok) {
				ans.push_back(val ^ x);
				break;
			}
		}
	}
	return ans;
}

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