Submission #894580

#	Time	Username	Problem	Language	Result	Execution time	Memory
894580		mychecksedad	Xoractive (IZhO19_xoractive)	C++17	100 / 100	4 ms	596 KiB

Xoractive

#include "interactive.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
int ask(int x);
vector<int> get_pairwise_xor(vector<int> positions);

int x;
map<int, vector<int>> p;
vector<int> dif(vector<int> a, vector<int> b){
	for(int i = 0; i < a.size(); ++i){
		int pos = lower_bound(all(b), a[i]) - b.begin();
		b.erase(b.begin() + pos);
	}
	// b.erase(b.begin());
	return b;
}
vector<int> get(vector<int> pos){
	vector<int> v = get_pairwise_xor(pos);
	vector<int> t;
	for(int i = int(sqrt(v.size())); i < v.size(); i += 2) t.pb(v[i]);
	return t;	
}
vector<int> learn_sorted(vector<int> v){
	vector<int> s1 = get(v);
	v.pb(1);
	vector<int> s2 = get(v);
	return dif(s1, s2);
}
set<int> s;
vector<int> guess(int n) {
	// cout << n << ' ' << "brh\n";
	vector <int> ans;

	x = ask(1);
	ans.pb(x);

	vector<int> pos;
	for(int j = 6; j >= 0; --j){
		pos.clear();
		for(int i = 2; i <= n; ++i){
			if(((i-2)&(1<<j)) == 0){
				pos.pb(i);
			}
		}
		vector<int> v = learn_sorted(pos);
		// for(int y: v) cout << y << ' ';
		// en;
		for(auto &y: v) y ^= x;
			// for(int y: v) cout << y << ' ';
			// en;
		for(int i = 0; i < v.size(); ++i) p[v[i]].pb(j), s.insert(v[i]);
	}
	// cout << x << ' ';
	vector<int> A;
	// for(auto y: A) cout << y << ' ' ;
	// cout << endl;
	for(int k: s) A.pb(k);
	sort(all(A), [&](const int &a, const int &b){
		for(int j = 0; j < p[a].size(); ++j){
			if(p[b].size() == j) return true;
			if(p[a][j] != p[b][j]) return p[a][j] > p[b][j];
		}
		// assert(false);
		return false;
	});
	for(int x: A) ans.pb(x);
	return ans;
}

Compilation message (stderr)

Xoractive.cpp: In function 'std::vector<int> dif(std::vector<int>, std::vector<int>)':
Xoractive.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i = 0; i < a.size(); ++i){
      |                 ~~^~~~~~~~~~
Xoractive.cpp: In function 'std::vector<int> get(std::vector<int>)':
Xoractive.cpp:26:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i = int(sqrt(v.size())); i < v.size(); i += 2) t.pb(v[i]);
      |                                   ~~^~~~~~~~~~
Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int i = 0; i < v.size(); ++i) p[v[i]].pb(j), s.insert(v[i]);
      |                  ~~^~~~~~~~~~
Xoractive.cpp: In lambda function:
Xoractive.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int j = 0; j < p[a].size(); ++j){
      |                  ~~^~~~~~~~~~~~~
Xoractive.cpp:66:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |    if(p[b].size() == j) return true;
      |       ~~~~~~~~~~~~^~~~

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