Submission #502608

#	Time	Username	Problem	Language	Result	Execution time	Memory
502608		Mazaalai	Xoractive (IZhO19_xoractive)	C++17	88 / 100	4 ms	456 KiB

Xoractive

#include "interactive.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define LINE "------------------\n"
#define ALL(x) x.begin(),x.end()
#define print(x) for(auto&el:x)cout<<el<<' ';cout<<'\n';
using namespace std;
using VI = vector <int>;
const int N = 105;
vector <int> ans;
int a1, n, answered;
// get_pairwise_xor, ask
VI getDif(vector <int>&a, vector <int>&b) {
	int i = 0, j = 0, x = a.size(), y = b.size();
	vector <int> res;
	while(i < x) {
		if (j < y && a[i] == b[j]) {
			i++, j++;
			continue;
		}
		res.pb(a[i++]);
	}
	return res;
}
VI getVals (VI ids) {
	VI ids1 = ids;
	ids1.pb(1);
	VI res = get_pairwise_xor(ids1);
	VI res1 = get_pairwise_xor(ids);
	VI vals = getDif(res, res1), ret;
	for (int i = 1; i < vals.size(); i+=2) ret.pb(vals[i]^a1);
	return ret;
}
void assign(int pos, int val) {
	answered++;
	ans[pos]=val;
}
vector<int> guess(int _n) {
	n = _n;
	a1 = ask(1);
	ans.resize(n);
	assign(0, a1); 
	vector <vector <pair <VI, VI> > >lvls(30);
	{
		VI ids, vals;
		for (int i = 2; i <= n; i++) ids.pb(i);
		vals = getVals(ids);
		lvls[0].pb(mp(ids, vals));
	}
	for (int lvl = 0; answered < n; lvl++) {
		VI queryIds;
		map <int, bool> isLeft;
		// divide;
		// cout << LINE;
		for (int i = 0; i < lvls[lvl].size(); i++) {
			VI& ids = lvls[lvl][i].ff;
			VI& vals = lvls[lvl][i].ss;
			// cout << "ids: "; print(ids);
			// cout << "vals: "; print(vals);
			// cout << '\n';
			int curSz = ids.size();
			for (int j = 0; j < curSz/2; j++) 
				queryIds.pb(ids[j]);
		}
		// find elements on the left side
		{
			// cout << "queryIds: ";print(queryIds);
			VI vals = getVals(queryIds);
			for (auto&el : vals) isLeft[el] = 1;

		}

		for (int i = 0; i < lvls[lvl].size(); i++) {
			VI& ids = lvls[lvl][i].ff;
			VI& vals = lvls[lvl][i].ss;
			VI lhs, rhs, valL, valR;
			int curSz = ids.size();
			// cout << "ids: "; print(ids);
			// cout << "vals: "; print(vals);
			for (int j = 0; j < curSz/2; j++) 
				lhs.pb(ids[j]);
			for (int j = curSz/2; j < curSz; j++) 
				rhs.pb(ids[j]);
			for (int j = 0; j < curSz; j++) {
				if (isLeft.count(vals[j])) valL.pb(vals[j]);
				else valR.pb(vals[j]);
			}
			// cout << "lhs: "; print(lhs);
			// cout << "valL: "; print(valL);
			// cout << "rhs: "; print(rhs);
			// cout << "valR: "; print(valR);
			if (lhs.size() == 1) assign(lhs[0]-1, valL[0]);
			else lvls[lvl+1].pb(mp(lhs, valL));
			if (rhs.size() == 1) assign(rhs[0]-1, valR[0]);
			else lvls[lvl+1].pb(mp(rhs, valR));
		}

	}
	// vals, ids -> vector <int> vals, vector <int> ids
	return ans;
}

Compilation message (stderr)

Xoractive.cpp: In function 'VI getVals(VI)':
Xoractive.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for (int i = 1; i < vals.size(); i+=2) ret.pb(vals[i]^a1);
      |                  ~~^~~~~~~~~~~~~
Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::vector<int>, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for (int i = 0; i < lvls[lvl].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~
Xoractive.cpp:60:8: warning: unused variable 'vals' [-Wunused-variable]
   60 |    VI& vals = lvls[lvl][i].ss;
      |        ^~~~
Xoractive.cpp:76:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::vector<int>, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for (int i = 0; i < lvls[lvl].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~

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