Submission #173719

#	Time	Username	Problem	Language	Result	Execution time	Memory
173719		Just_Solve_The_Problem	Xoractive (IZhO19_xoractive)	C++11	6 / 100	14 ms	2424 KiB

Xoractive

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

#define ok puts("ok");

using namespace std;

int pw[123];
vector <int> ar;
vector <int> vec[12345], vv[1234];
multiset <int> ss[1234];
int nn;

int Ask(int x) {
	if (ar[x] != -1) return ar[x];
	return ar[x] = ask(x + 1);
}

// BIG, SMALL
vector <int> get(int x, vector <int> pos1, vector<int> pos2) {
	multiset <int> s;
	for (int to : pos1) {
		s.insert(to);
	}
	for (int to : pos2) {
		s.erase(s.find(to));
	}
	vector <int> vec;
	int c1 = 0;
	for (int to : s) {
		if (c1 & 1 ^ 1) {
			vec.push_back(to ^ x);
		}
		c1++;
	}
	return vec;
}

// Big, SMALL
vector <int> ex(vector <int> p1, vector <int> p2) {
	int c = 0;
	vector <int> ans;
	sort(p1.begin(), p1.end());
	sort(p2.begin(), p2.end());
	for (int to : p1) {
		if (to == p2[c]) {
			c++;
		} else {
			ans.push_back(to);			
		}
	}
	return ans;
}


// big, small
vector <int> in(vector <int> p2, vector <int> p1) {
	int c = 0;
	multiset <int> s;
	vector <int> ans;
	for (int to : p2) {
		s.insert(to);
	}
	for (int to : p1) {
		if (s.count(to)) {
			ans.push_back(to);
			s.erase(s.find(to));
		}
	}
	return ans;
}


void go(int v, int l, int r, int lvl, int ind) {
	/*
	cout << v << ' ' << l << ' ' << r << ' ' << lvl << ' ' << ind << endl;
	for (int to : vv[v]) {
		cout << to << ' ';
	}
	cout << endl;
	*/
	int len = (1 << lvl - 1);
	if (lvl == 0) {
		ar[(1 << pw[nn - 1]) - 1 - ind] = vv[v][0];
		return ;
	}
	vv[v + v] = in(vv[v], vec[lvl - 1]);
	go(v + v, l, l + len - 1, lvl - 1, ind + len);
	if (l + len < nn) {
		vv[v + v + 1] = ex(vv[v], vv[v + v]);
		go(v + v + 1, l + len, min(nn - 1, r), lvl - 1, ind);
	}
}

vector<int> guess(int _n) {
	nn = _n;
	vector<int> forask[2];
	ar.resize(nn, -1);
	for (int i = 1; i <= nn; i++) {
		pw[i] = pw[i / 2] + 1;
	}
	for (int i = pw[nn - 1]; i >= 0; i--) {
		int lvl = (1 << i);
		for (int k = 0; k < 2; k++) 
			forask[k].clear();
		for (int j = 0; j < nn; j += lvl + lvl) {
			for (int k = j; k < min(j + lvl, nn); k++) {
				forask[0].push_back(k + 1);
				if (k != 0)
					forask[1].push_back(k + 1);
			}
		}
		vec[i] = get(Ask(0), get_pairwise_xor(forask[0]), get_pairwise_xor(forask[1]));
		for (int to : vec[i]) {
			ss[i].insert(to);
		}
	}
	vv[1] = vec[pw[nn - 1]];
	go(1, 0, nn - 1, pw[nn - 1], 0);
	return ar;
}

Compilation message (stderr)

Xoractive.cpp: In function 'std::vector<int> get(int, std::vector<int>, std::vector<int>)':
Xoractive.cpp:32:10: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   if (c1 & 1 ^ 1) {
       ~~~^~~
Xoractive.cpp: In function 'std::vector<int> in(std::vector<int>, std::vector<int>)':
Xoractive.cpp:59:6: warning: unused variable 'c' [-Wunused-variable]
  int c = 0;
      ^
Xoractive.cpp: In function 'void go(int, int, int, int, int)':
Xoractive.cpp:83:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  int len = (1 << lvl - 1);
                  ~~~~^~~

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