Cod sursa(job #1072188)

Utilizator VincentVegaVincent Vega VincentVega Data 4 ianuarie 2014 09:57:26
Problema Xor Max Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

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

struct Trie
{
	Trie *son[2];
	int p;
	
	Trie()
	{
		memset(son, 0, sizeof(son));
	}
};

Trie *T = new Trie;
int N, A, R = -1, S, F, Y;
int bits[24];

void take_bits(int A)
{
	bits[0] = 0;
	
	if (A == 0)
	{
		for (int i = 1; i <= 22; ++i)
			bits[++bits[0]] = 0;
		return ;
	}
	
	while (A)
	{
		bits[++bits[0]] = A % 2;
		A = A / 2;
	}
	
	while (bits[0] < 22)
		bits[++bits[0]] = 0;
		
	reverse(bits + 1, bits + bits[0] + 1);
}

inline void insert(Trie *T, const int &i)
{
	if (i > bits[0])
	{
		T->p = Y;
		return ;
	}
	
	if (T->son[bits[i]] == 0)
		T->son[bits[i]] = new Trie;
	
	insert(T->son[bits[i]], i + 1);
}

inline int get_max(Trie *T, const int &i)
{
	if (i > bits[0])
	{
		Y = T->p;
		return 0;
	}
	
	if (T->son[!bits[i]])
		return get_max(T->son[!bits[i]], i + 1) + (1 << (bits[0] - i));
	
	if (T->son[bits[i]])
		return get_max(T->son[bits[i]], i + 1);
		
	return 0;
}

int main()
{
	fin >> N;
	insert(T, 1);
	for (int i = 1; i <= N; ++i)
	{
		int X;
		
		fin >> X;
		A = A ^ X;
		
		take_bits(A);
		int V = get_max(T, 1);
		
		if (R < V || (R == V && F - S > i - Y))
		{
			R = V;
			S = Y;
			F = i;
		}
		
		Y = i;
		insert(T, 1);
	}
	
	fout << R << ' ' << S + 1 << ' ' << F << '\n';
	fin.close();
	fout.close();
}