Cod sursa(job #2909607)

Utilizator lolismekAlex Jerpelea lolismek Data 14 iunie 2022 11:57:15
Problema Xor Max Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <cmath>

#define pii pair <int, int>

using namespace std;

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

const int SIGMA = 2, P = 21;

struct trie{
	int poz;
	trie *nxt[SIGMA];
};

trie root;

void insertTrie(trie *nod, int val, int bit, int i){
	if(bit < 0){
		nod -> poz = i;
		return;
	}

	int ind = (val & (1 << bit)) != 0;
	if(nod -> nxt[ind] == NULL)
		nod -> nxt[ind] = new trie();


	insertTrie(nod -> nxt[ind], val, bit - 1, i);
}

 pii findTrie(trie *nod, int val, int bit, int ans){
 	if(bit < 0)
 		return {ans, nod -> poz};
 	
 	int ind = (val & (1 << bit)) != 0;

 	ind = !ind;

 	if(nod -> nxt[ind] == NULL)
 		ind = !ind;

 	return findTrie(nod -> nxt[ind], val, bit - 1, ans + ind * (1 << bit));
 }

int main(){
	
	int n, Xsum = 0, maxi = -1;
	fin >> n;
	insertTrie(&root, 0, P, 0);

	int l = 0, r = 0;

	for(int i = 1; i <= n; i++){
		int x;
		fin >> x;
		Xsum ^= x;

		pii tmp = findTrie(&root, Xsum, P, 0);

		if((tmp.first ^ Xsum) > maxi){
			maxi = (tmp.first ^ Xsum);
			l = tmp.second + 1;
			r = i;
		}

		insertTrie(&root, Xsum, P, i);
	}

	fout << maxi << ' ' << l << ' ' << r << '\n';

	return 0;
}