Pagini recente » Cod sursa (job #2374956) | Cod sursa (job #1636721) | Cod sursa (job #739865) | Cod sursa (job #554525) | Cod sursa (job #2364805)
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
const int NR_BITS = 21;
const int N_MAX = 100001;
int N;
int secv[N_MAX];
struct Trie {
Trie *fiu[2]; //putem aveam maxim 2 fii (pentru bitii 0 si 1)
//constructor
Trie() {
memset(fiu, 0, sizeof(fiu));
}
};
Trie *T = new Trie;
void insert(Trie *nod, int n, int b) {
if(b == 0)
return;
int bit = (n & b) ? 1 : 0;
if(nod->fiu[bit] == 0) //daca nu exista fiu, alocam memorie
nod->fiu[bit] = new Trie;
insert(nod->fiu[bit], n, b >> 1); //trecem la nivelul urmator, cu bitul urmator
}
int search(Trie * nod, int n, int res, int b) {
if(nod->fiu[0] == 0 && nod->fiu[1] == 0) //daca nu exista fii
return res;
int bit = (n & b) ? 1 : 0;
if(nod->fiu[bit ^ 1]) //daca exista numar cu bitul opus lui q
return search(nod->fiu[bit ^ 1], n, res + b, b >> 1);
if(nod->fiu[bit]) //daca nu exista numar cu bit opus, dar exista cu acelasi bit ca si q
return search(nod->fiu[bit], n, res, b >> 1);
}
int nr_bits(int x) {
int nr = 0;
while((1 << nr) <= x)
nr++;
return nr;
}
int main() {
int x, nrbits = 0, xormax = -1, start, finish, ans;
in >> N;
secv[0] = 0;
for(int i = 1; i <= N; ++i) {
in >> x;
secv[i] = secv[i - 1] ^ x;
nrbits = max(nrbits, nr_bits(secv[i]));
}
insert(T, 0, 1 << (nrbits - 1));
for(int i = 1; i <= N; ++i) {
ans = search(T, secv[i], 0, 1 << (nrbits - 1));
if(ans > xormax) {
xormax = ans;
finish = i;
}
insert(T, secv[i], 1 << (nrbits - 1));
}
for(int i = 0; i < finish; ++i)
if((secv[i] ^ secv[finish]) == xormax)
start = i + 1;
out << xormax << ' ' << start << ' ' << finish;
return 0;
}