제출 #1132283

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132283		Muhammet	Xoractive (IZhO19_xoractive)	C++17	100 / 100	4 ms	544 KiB

Xoractive

#include <bits/stdc++.h>
#include "interactive.h"
// #include "grader.cpp"

using namespace std;

#define SZ(s) (int)s.size()
#define ff first
#define ss second

int x;

map <int,int> vis, vis1, mp;

vector <int> get(vector <int> v, int n){
	vector <int> v1, v2, v3;
	v.push_back(n);
	v1 = get_pairwise_xor(v);
	v.pop_back();
	v2 = get_pairwise_xor(v);
	vis.clear(), vis1.clear();
	vis[0]++;
	for(auto i : v2) {
		vis[i]++;
	}
	for(auto i : v1) {
		if(vis[i]) vis[i]--;
		else {
			if(vis1[i^x] == 0){
				vis1[i^x] = true;
				v3.push_back(i^x);
			}
		}
	}
	return v3;
}

vector<int> guess(int n) {
	x = (ask(n));
	vector <vector <int>> vc, vc1;
	vector <pair<int,int>> ve, ve1;
	vc.push_back({0});
	ve.push_back({1,n});
	vector <int> ans(n,0);
	while(SZ(vc) > 0) {
		vector <int> v;
		for(int i = 0; i < SZ(vc); i++){
			int l = ve[i].ff, r = ve[i].ss;
			// cout << l << ' ' << r << '\n';
			for(int j = l; j <= ((l + r) / 2); j++){
				if(j == n) continue;
				v.push_back(j);
			}
		}
		// cout << '\n';
		if(SZ(v) == 0) break;
		vector <int> v3 = get(v,n);
		for(int i = 0; i < SZ(vc); i++){
			vector <int> vec;
			int l = ve[i].ff, r = ve[i].ss;
			if(SZ(vc[i]) == 1) {
				for(auto j : v3){
					if(vis1[j] == true) vec.push_back(j);
				}
				if(SZ(vec) == 1) ans[l-1] = vec[0];
				else vc1.push_back(vec), ve1.push_back({l,(l+r)/2});
				if((r-l+1) - SZ(vec) == 1) continue;
				else vc1.push_back({0}), ve1.push_back({(l+r)/2+1,r});
				continue;
			}
			for(auto j : vc[i]){
				if(vis1.find(j) != vis1.end()) vec.push_back(j);
			}
			if(SZ(vec) == 1) ans[l-1] = vec[0];
			else vc1.push_back(vec), ve1.push_back({l,(l+r)/2});
			vec.clear();
			for(auto j : vc[i]){
				if(vis1.find(j) == vis1.end()) vec.push_back(j);
			}
			if(SZ(vec) == 1) ans[r-1] = vec[0];
			else vc1.push_back(vec), ve1.push_back({(l+r)/2+1,r});
			for(auto j : vc[i]){
				if(vis1.find(j) != vis1.end()) vis1[j] = false;
			}
			vec.clear();
		}
		vc = vc1;
		vc1.clear();
		ve = ve1;
		ve1.clear();
	}
	ans[n-1] = x;
	// ans[0] = x;
	// ans[n-1] = ask(n);
	return ans;
}

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