Cod sursa(job #2704481)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 10 februarie 2021 17:42:54
Problema Xor Max Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;

struct Node{
	Node* ch[2];
	int index;
	
	Node()
	{
		ch[0] = ch[1] = NULL;
		index = -1;
	}
};	


vector<int> query(Node* root, int val)
{
	vector<int> ans(2);
	
	ans[0] = 0;
	for(int i = 25;i >= 0 && root;--i)
	{
		int bit = 0;
		if(val & (1 << i))
			bit = 1;
		if(root->ch[1 - bit])
		{
			ans[0] |= 1 << i;
			root = root->ch[1 - bit];
		}
		else
			root = root->ch[bit];
	}
	if(root)
		ans[1] = root->index;
	return ans;	
}

void insert(Node* root, int val, int index)
{
	for(int i = 25;i >= 0;--i)
	{
		int bit = 0;
		if(val & (1 << i))
			bit = 1;
		if(root->ch[bit] == NULL)
			root->ch[bit] = new Node();
		root = root->ch[bit];
	}
	root->index = index;
}

vector<int> solve(vector<int>& v, Node* root)
{
	int n = v.size(), xor_pref = 0;
	vector<int> ans(3);
	ans[0] = 0;
	
	for(int i = 0;i < n;++i)
	{
		xor_pref ^= v[i];
		if(xor_pref > ans[0])
		{
			ans[0] = xor_pref;
			ans[1] = 0;
			ans[2] = i;
		}
		vector<int> ret = query(root, xor_pref);
		if(ret[0] > ans[0])
		{
			ans[0] = ret[0];
			ans[1] = ret[1] + 1;
			ans[2] = i;
		}
		insert(root, xor_pref, i);
	}
	return ans;
}

int main()
{
	ifstream in("xormax.in");
	ofstream out("xormax.out");
	
	int n;
	in >> n;

	vector<int> v(n);
	for(int i = 0;i < n;++i)
		in >> v[i];
	Node* root = new Node();
	vector<int> ans = solve(v, root);
	out << ans[0] << " " << ans[1] + 1 << " " << ans[2] + 1 << "\n";
	in.close();
	out.close();
}