제출 #1132273

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132273		Muhammet	Xoractive (IZhO19_xoractive)	C++17	88 / 100	6 ms	788 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

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

vector<int> guess(int n) {
	vector <int> v, v1, v2;
	int x = (ask(1));
	mp[1] = x;
	vector <vector <int>> vc, vc1;
	vector <pair<int,int>> ve, ve1;
	vc.push_back({0});
	ve.push_back({2,2*(n-1)});
	int cnt = -1;
	while(SZ(vc) > 0) {
		v.clear(), v1.clear(), v2.clear();
		cnt++;
		for(int i = 0; i < SZ(vc); i++){
			int l = ve[i].ff, r = ve[i].ss;
			for(int j = l; j <= ((l + r) / 2); j++){
				v.push_back(j);
			}
		}
		if(SZ(v) == 0) break;
		v.push_back(1);
		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]++;
		}
		vector <int> v3;
		for(auto i : v1) {
			if(vis[i] > 0) vis[i]--;
			else {
				if(vis1[i^x] == 0){
					vis1[i^x] = true;
					v3.push_back(i^x);
				}
			}
		}
		if(!cnt){
			vc[0] = v3;
			ve[0] = {2,n};
			continue;
		}
		for(int i = 0; i < SZ(vc); i++){
			vector <int> vec;
			int l = ve[i].ff, r = ve[i].ss;
			for(auto j : vc[i]){
				if(vis1.find(j) != vis1.end()) vec.push_back(j);
			}
			if(SZ(vec) == 1) mp[l] = 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) mp[r] = vec[0];
			else vc1.push_back(vec), ve1.push_back({(l+r)/2+1,r});
			vec.clear();
		}
		vc.clear();
		vc = vc1;
		vc1.clear();
		ve.clear();
		ve = ve1;
		ve1.clear();
	}
	vector <int> ans;
	for(int i = 1; i <= n; i++){
		ans.push_back(mp[i]);
	}
	return ans;
}

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