Cod sursa(job #2908531)

Utilizator MarcGrecMarc Grec MarcGrec Data 4 iunie 2022 10:21:10
Problema Xor Max Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#define MAX_N 100000
#define MAX_BIT 21

#include <fstream>
using namespace std;

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

struct Node
{
	int index;
	Node *next[2];
} *root = new Node();

void insert(const int value, const int index)
{
	Node *current = root;
	for (int bit = MAX_BIT; bit >= 0; --bit)
	{
		const int option = (value >> bit) & 1;
		if (!current->next[option])
			current->next[option] = new Node();
		current = current->next[option];
	}
	current->index = index;
}

void retrieve(const int value, int& out_value, int& out_index)
{
	out_value = 0;
	Node *current = root;
	for (int bit = MAX_BIT; bit >= 0; --bit)
	{
		int option = ((value >> bit) & 1) ^ 1;
		if (!current->next[option])
			option ^= 1;
		current = current->next[option];
		out_value |= option << bit;
	}
	out_index = current->index;
}

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

int n, x, ri, rj, rxi, rxj;

int main()
{
	fin >> n;
	ri = rj = 1;
	for (int j = 1, xj = 0; j <= n; ++j)
	{
		insert(xj, j - 1);
		fin >> x;
		xj ^= x;
		int i, xi;
		retrieve(xj, xi, i);
		if ((xj ^ xi) > (rxj ^ rxi))
		{
			ri = i;
			rj = j;
			rxi = xi;
			rxj = xj;
		}
	}
	fout << (rxj ^ rxi) << ' ' << (ri + 1) << ' ' << rj;
	cleanup(root);
    fin.close();
    fout.close();
    return 0;
}