Cod sursa(job #3120956)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 9 aprilie 2023 20:08:18
Problema Xor Max Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <bits/stdc++.h>
#define NMAX 100005
#define MAX (1 << 23)
using namespace std;

int xuma[NMAX];
int trie[MAX];

void add_trie(int x) {
	for (int b = 20, pos = 1; b >= 0; --b) {
		trie[pos] = 1;
		if ((1 << b) & x) {
			pos = (pos << 1) + 1;
		} else {
			pos <<= 1;
		}
	}
}

int search_trie(int x) {
	int best = 0;
	for (int b = 20, pos = 1; b >= 0; --b) {
		if ((1 << b) & x) {
			if (trie[pos << 1]) {
				pos <<= 1;
			} else {
				best |= (1 << b);
				pos = (pos << 1) + 1;
			}
		} else {
			if (trie[(pos << 1) + 1]) {
				best |= (1 << b);
				pos = (pos << 1) + 1;
			} else {
				pos <<= 1;
			}
		}
	}

	return best;
}

void solve()
{
	int n;
	cin >> n;

	for (int i = 1, x; i <= n; ++i) {
		cin >> x;
		xuma[i] = xuma[i - 1] ^ x;
	}

	add_trie(0);

	int ans = xuma[1], left = 1, right = 1;
	for (int i = 1; i <= n; ++i) {
		int aux = search_trie(xuma[i]);
		if (ans < (xuma[i] ^ aux)) {
			ans = xuma[i] ^ aux;
			left = aux;
			right = i;
		}

		add_trie(xuma[i]);
	}

	for (int i = 0; i < n; ++i)
		if (xuma[i] == left) {
			left = i + 1;
			break;
		}

	cout << ans << ' ' << left << ' ' << right << '\n';
}

int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int t = 1;
	// cin >> t;
	while(t--)
		solve();

	return 0;
}