Submission #784648

#	Time	Username	Problem	Language	Result	Execution time	Memory
784648		PoonYaPat	Xoractive (IZhO19_xoractive)	C++14	88 / 100	8 ms	524 KiB

Xoractive

#include "interactive.h"
#include <bits/stdc++.h>
using namespace std;

struct range {
	int l,r;
	vector<int> val;
};

int st,ans[105];

vector<int> del(vector<int> r1, vector<int> r2) {
	vector<int> res;
	priority_queue<int> pq1,pq2;
	for (auto s : r1) pq1.push(s);
	for (auto s : r2) pq2.push(s);

	while (pq1.size()) {
		if (pq1.top()==pq2.top()) {
			pq1.pop();
			pq2.pop();
		} else {
			res.push_back(pq1.top());
			pq1.pop();
		}
	}
	
	reverse(res.begin(),res.end());
	return res;
}

void solve(vector<range> v) {
	map<int,bool> have;
	vector<range> nxt;
	vector<int> temp1,temp2;
	temp1.push_back(1);

	for (auto s : v) {
		int mid=(s.l+s.r)/2;
		for (int i=s.l; i<=mid; ++i) temp1.push_back(i), temp2.push_back(i);
	}

	vector<int> res=del(get_pairwise_xor(temp1),get_pairwise_xor(temp2));

	for (int i=1; i<res.size(); i+=2) have[res[i]^st]=true;
	for (auto s : v) {
		vector<int> L,R;
		int mid=(s.l+s.r)/2;
		for (auto k : s.val) {
			if (have[k]) L.push_back(k);
			else R.push_back(k);
		}

		if (s.l==mid) ans[s.l]=L[0];
		else nxt.push_back({s.l,mid,L});

		if (mid+1==s.r) ans[s.r]=R[0];
		else nxt.push_back({mid+1,s.r,R});
	}

	if (nxt.size()) solve(nxt);
}


vector<int> guess(int n) {
	st=ask(1);
	ans[1]=st;
	vector<int> v1,v2,temp,res;
	v1.push_back(1);
	for (int i=2; i<=n; ++i) v1.push_back(i), v2.push_back(i);
	temp=del(get_pairwise_xor(v1),get_pairwise_xor(v2));
	for (int i=1; i<temp.size(); i+=2) res.push_back(temp[i]^st);
	solve({{2,n,res}});

	vector<int> Ans;
	for (int i=1; i<=n; ++i) Ans.push_back(ans[i]);
	return Ans;
}

Compilation message (stderr)

Xoractive.cpp: In function 'void solve(std::vector<range>)':
Xoractive.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int i=1; i<res.size(); i+=2) have[res[i]^st]=true;
      |                ~^~~~~~~~~~~
Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:72:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for (int i=1; i<temp.size(); i+=2) res.push_back(temp[i]^st);
      |                ~^~~~~~~~~~~~

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