Cod sursa(job #2623402)

Utilizator MarcGrecMarc Grec MarcGrec Data 3 iunie 2020 09:20:48
Problema Xor Max Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#define MAX_N 100000
#define DELTA 21
#define INF 0x3f3f3f3f

#include <fstream>
using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

struct trienode
{
	trienode()
	{
		index = -1;
		N[0]  = N[1] = nullptr;
	}
	
	int index;
	trienode* N[2];
} *root = new trienode;

int n, DP[MAX_N + 1];
int I = -1, J = -1, MA = -INF;

void TryUpdate(int value);
void Insert(int value);
void DeleteTrie(trienode* &node);

int main()
{
	fin >> n;
	for (int i = 1, x; i <= n; ++i)
	{
		fin >> x;
		DP[i] = DP[i - 1] ^ x;
	}
	
	Insert(0);
	for (int i = 1; i <= n; ++i)
	{
		TryUpdate(i);
		Insert(i);
	}
	
	fout << MA << ' ' << (I + 1) << ' ' << J;
	
	DeleteTrie(root);
	
	fin.close();
	fout.close();
	return 0;
}

int VALUE, INDEX, PARTNER;

void GetPartner(trienode* node, int index)
{	
	if (index == 1)
	{
		INDEX = node->index;
	}
	else
	{
		const bool bit = (VALUE >> (index - 1)) & 1;
		
		if (node->N[!bit] != nullptr)
		{
			PARTNER |= (!bit) << (index - 1);
			GetPartner(node->N[!bit], index - 1);
		}
		else
		{
			PARTNER |= bit << (index - 1);
			GetPartner(node->N[bit], index - 1);
		}
	}
}

void TryUpdate(int index)
{
	VALUE   = DP[index];
	PARTNER = 0;
	INDEX   = 0;
		
	if (root->N[0] != root->N[1])
	{
		GetPartner(root, DELTA - 1);
	}
	
	if (MA < (PARTNER ^ VALUE))
	{
		MA = PARTNER ^ VALUE;
		I  = INDEX;
		J  = index;
		
		if (I == 0)
		{
			I = index - 1;
		}
	}
}

void InsertInNode(trienode* &node, int index)
{
	if (node == nullptr)
	{
		node = new trienode;
	}
	
	if (index == 1)
	{
		node->index = INDEX;
	}
	else
	{
		const bool bit = (VALUE >> (index - 1)) & 1;
		
		InsertInNode(node->N[bit], index - 1);
	}
}

void Insert(int index)
{
	VALUE = DP[index];
	INDEX = index;
	InsertInNode(root, DELTA - 1);
}

void DeleteTrie(trienode* &node)
{
	if (node != nullptr)
	{
		DeleteTrie(node->N[0]);
		DeleteTrie(node->N[1]);
		
		delete node;
		node = nullptr;
	}
}