Cod sursa(job #1468742)

Utilizator greenadexIulia Harasim greenadex Data 6 august 2015 21:12:08
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair

using namespace std;

const string name = "xormax",
             in_file = name + ".in",
             out_file = name + ".out";

ifstream fin(in_file);
ofstream fout(out_file);

const int MAX = 1e5 + 5;
int maxx, s[MAX], n, maxi, maxj, max_sum;

struct Trie {
	int index;
	Trie* f[2];

	Trie() {
		memset(f, 0, sizeof(f));
		index = 0;
	}
};

Trie * root = new Trie();

void add_sum(Trie* nod, int sum, int poz, int i) {
	if (poz == -1) {
		nod -> index = i;
		return;
	}
	int bit = ((1 << poz) & sum ? 1 : 0);
	if (nod -> f[bit] == NULL)
		nod -> f[bit] = new Trie();

	add_sum(nod -> f[bit], sum, poz - 1, i);
}

int xor_max(Trie* nod, int sum, int poz, int& maxx) {
	if (poz == -1)
		return nod -> index;

	int bit = ((1 << poz) & sum ? 0 : 1);
	if (nod -> f[bit] != NULL)
		maxx = ((1 << poz) ^ maxx);
	else
		bit = (bit ? 0 : 1);

	xor_max(nod -> f[bit], sum, poz - 1, maxx);
}

int main() {
	fin >> n;
	for (int temp, nr, i = 1; i <= n; i++) {
		fin >> nr;

		s[i] = s[i - 1] ^ nr;
		add_sum(root, s[i], 20, i);

		maxx = 0;
		temp = xor_max(root, s[i], 20, maxx);
		if (maxx > max_sum) {
			max_sum = maxx;
			maxi = temp + 1;
			maxj = i;
		}
	}
	fout << max_sum << ' ' << maxi << ' ' << maxj;
	return 0;
}