제출 #337776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
337776		tengiz05	Xoractive (IZhO19_xoractive)	C++17	100 / 100	12 ms	1792 KiB

Xoractive

#include "interactive.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int msb(int val){return sizeof(int)*8-__builtin_clz(val)-1;}
vector<int> guess(int n) {
	vector <int> ans(n);
	vector<multiset<int>> v(8);
	vector<multiset<int>> o(8);
	ans[0] = ask(1);
	for(int j=0;j<7;j++){
		vector<int> todo;
		for(int i=2;i<=n;i++){
			if(i&(1<<j))todo.pb(i);
		}if(todo.empty())continue;
		vector<int> tmp = get_pairwise_xor(todo);
		for(auto x : tmp){
			v[j].insert(x);
		}todo.pb(1);
		tmp = get_pairwise_xor(todo);
		for(auto x : tmp){
			o[j].insert(x);
		}
	}
 
	for(int i=0;i<7;i++){
		for(auto x : v[i]){
			o[i].erase(o[i].find(x));
		}
	}
	for(int i=2;i<=n;i++){
		multiset<int> res;
		for(auto x : o[msb(i)])res.insert(x);
		for(int j=0;j<7;j++){
			if(i&(1<<j)){
				vector<int> toerase;
				for(auto x : res)if(o[j].find(x) == o[j].end())toerase.pb(x);
				for(auto x : toerase)res.erase(res.find(x));
			}else {
				for(auto x : o[j]){
					if(res.find(x) != res.end())res.erase(res.find(x));
				}
			}
		}
		assert(res.size());
		ans[i-1] = (*res.rbegin())^ans[0];
	}
	return ans;
}
 

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