Cod sursa(job #2300115)

Utilizator florin_salamFlorin Salam florin_salam Data 10 decembrie 2018 21:32:24
Problema Xor Max Scor 100
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>

using namespace std;

class node
{
public:
	int pos;
	node* v[2];
	node()
	{
		this->pos = 0;
		this->v[0] = this->v[1] = NULL;
	}
	~node()
	{
		if (this->v[0] != NULL)
			delete this->v[0];
		if (this->v[1] != NULL)
			delete this->v[1];
	}
};

class trie
{
public:
	trie()
	{
		root = new node();
	}
	~trie()
	{
		delete root;
	}
	int Query(const int &x)
	{
		return RecursiveQuery(root, x, 20);
	}
	void Add(const int &x, const int &pos)
	{
		RecursiveAdd(root, x, 20, pos);
	}
private:
	int RecursiveQuery(node* currNode, const int &val, int bitPos)
	{
		if (bitPos == -1)
			return currNode->pos;
		if (currNode->v[1 - (((1 << bitPos) & val) > 0)] != NULL)
			return RecursiveQuery(currNode->v[1 - (((1 << bitPos) & val) > 0)], val, bitPos - 1);
		else 
			return RecursiveQuery(currNode->v[(((1 << bitPos) & val) > 0)], val, bitPos - 1);
	}
	void RecursiveAdd(node* currNode, const int &val, int bitPos, const int &valPos)
	{
		if (bitPos == -1)
		{
			currNode->pos = valPos;
			return;
		}
		if (currNode->v[(((1 << bitPos) & val) > 0)] == NULL)
			currNode->v[(((1 << bitPos) & val) > 0)] = new node();
		RecursiveAdd(currNode->v[(((1 << bitPos) & val) > 0)], val, bitPos - 1, valPos);
	}
	node *root;
};

const int NMAX = 1e5 + 5;
int n, s[NMAX];
trie T;

int main()
{
	ifstream fin("xormax.in");
	ofstream fout("xormax.out");
	int stg = 0, drp = 0, valMax = -1;
	fin >> n;
	for (int i = 1;i <= n;++i)
	{
		fin >> s[i];
		s[i] ^= s[i - 1];
	}
	T.Add(0, 0);
	for (int i = 1;i <= n;++i)
	{
		int aux = T.Query(s[i]);
		if ((s[i] ^ s[aux]) > valMax)
		{
			stg = aux + 1;
			drp = i;
			valMax = s[i] ^ s[aux];
		}
		T.Add(s[i], i);
	}
	fout << valMax << " " << stg << " " << drp << "\n";
	fin.close();
	fout.close();
	return 0;
}