Cod sursa(job #3307063)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 16 august 2025 20:36:49
Problema Xor Max Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <algorithm>
#include <fstream>
#include <vector>
#define ll long long

using namespace std;

const string txt = "xormax";
const int nmax = 1e5 + 5;

ifstream f(txt + ".in");
ofstream g(txt + ".out");

struct trie {
	trie* nxt[5];
	int poz;

	trie() {
		nxt[0] = nxt[1] = NULL; poz = 0;
	}
};

int n, v[nmax], maxi = -1, st, dr;

static void add(int x, int b, int ind, trie* nod)
{
	if (b == 0) {
		if (!nod -> poz)
			nod -> poz = ind;
		
		return;
	}

	int vec = (x & (1 << b) ? 1 : 0);

	if (!nod -> nxt[vec])
		nod -> nxt[vec] = new trie;

	add(x, b - 1, ind, nod -> nxt[vec]);
}

static int query(int x, int b, trie* nod)
{
	if (b == 0)
		return nod->poz;
	
	int vec = (x & (1 << b) ? 0 : 1);

	if (!nod -> nxt[vec])
		return query(x, b - 1, nod -> nxt[1 - vec]);
	
	return query(x, b - 1, nod -> nxt[vec]);
}

int main()
{
	trie* rad = new trie;
	add(0, 20, 0, rad);

	f >> n;
	for (int i = 1; i <= n; i++)
	{
		int x; f >> x;
		v[i] = (v[i - 1] ^ x);
		
		int poz = query(v[i], 20, rad);

		if (maxi < (v[i] ^ v[poz]))
			maxi = (v[i] ^ v[poz]), st = poz + 1, dr = i;

		//else if (maxi == (v[i] ^ v[poz]) && st > poz + 1)
		//	st = poz + 1, dr = i;
			
		add(v[i], 20, i, rad);
	}

	g << maxi << " " << st << " " << dr;
	return 0;
}