Cod sursa(job #2300075)

Utilizator florin_salamFlorin Salam florin_salam Data 10 decembrie 2018 20:40:07
Problema Xor Max Scor 30
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 2.03 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)
		{
			if (currNode->pos == 0)
				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, drp, valMax, x, lgMin;
	fin >> n;
	fin >> s[1];
	stg = drp = 1;
	lgMin = 1;
	valMax = s[1];
	T.Add(s[1], 1);
	for (int i = 2;i <= n;++i)
	{
		fin >> x;
		s[i] = s[i - 1] ^ x;
		int aux = T.Query(s[i]);
		if ((s[i] ^ s[aux]) > valMax)
		{
			stg = aux + 1;
			drp = i;
			lgMin = drp - stg + 1;
			valMax = s[i] ^ s[aux];
		}
		else if ((s[i] ^ s[aux]) == valMax)
		{
			if (i - aux < lgMin)
			{
				drp = i;
				stg = aux;
				lgMin = drp - stg + 1;
			}
		}
		T.Add(s[i], i);
	}
	fout << valMax << " " << stg << " " << drp << "\n";
	fin.close();
	fout.close();
	return 0;
}