Cod sursa(job #2930394)

Utilizator MarcGrecMarc Grec MarcGrec Data 28 octombrie 2022 12:34:35
Problema Xor Max Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#define MAX_N 100000
#define BITS 21

#define GET_RANGE(start, stop) (a[(start) - 1] ^ a[(stop)])

#include <fstream>
using namespace std;

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

int n, a[MAX_N + 1];

struct node
{
	int index = 0;
	node* next[2] = { nullptr, nullptr };
} *root = new node();

void add(int index)
{
	node* current = root;
	for (int i = BITS - 1; i >= 0; --i)
	{
		int bit = (a[index] >> i) & 1;
		if (!current->next[bit])
			current->next[bit] = new node();
		current = current->next[bit];
	}
	current->index = index;
}

int search(int value)
{
	node* current = root;
	for (int i = BITS - 1; i >= 0; --i)
	{
		int bit = ((value >> i) & 1) ^ 1;
		if (!current->next[bit])
			bit ^= 1;
		current = current->next[bit];
	}
	return current->index;
}

void cleanup(node* &current)
{
	if (current)
	{
		cleanup(current->next[0]);
		cleanup(current->next[1]);
		delete current;
		current = nullptr;
	}
}

int main()
{
	fin >> n;
	for (int i = 1; i <= n; ++i)
	{
		fin >> a[i];
		a[i] ^= a[i - 1]; 
		// a[i] ^ a[j] = b[i + 1] ^ ... ^ b[j]
		// a[0] ^ a[j] = b[1] ^ ... ^ b[j]
	}
	add(0);
	int startf = 1, stopf = 1;
	for (int stop = 2; stop <= n; ++stop)
	{
		int start = search(a[stop]) + 1;
		if (GET_RANGE(startf, stopf) < GET_RANGE(start, stop))
		{
			startf = start;
			stopf = stop;
		}
		add(stop);
	}
	fout << GET_RANGE(startf, stopf) << ' ' << startf << ' ' << stopf;
	cleanup(root);
    fin.close();
    fout.close();
    return 0;
}