Pagini recente » Cod sursa (job #1249685) | Cod sursa (job #2989556) | Cod sursa (job #2932359) | Cod sursa (job #1647925) | Cod sursa (job #850755)
Cod sursa(job #850755)
#include <fstream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
struct trie{
trie *sons[2];
int loc;
trie(){
sons[0]=sons[1]=0;
}
};
trie *root = new trie;
int xr[100001];
int tar,mx,in1,in2;
int dafuq;
void add(trie *tri, int i) {
if (i == -1) {
tri->loc = tar;
}
else {
if (((1<<i)|xr[tar]) == xr[tar]) {
if (!tri->sons[1])
tri->sons[1] = new trie;
add(tri->sons[1],i-1);
}
else {
if (!tri->sons[0])
tri->sons[0] = new trie;
add(tri->sons[0],i-1);
}
}
}
void find(trie *tri, int i) {
if (i == -1) {
if (((xr[tar])^(xr[tri->loc]))>mx) {
mx = ((xr[tar])^(xr[tri->loc]));
in1=(tri->loc)+1;
in2=tar;
}
}
else {
if (((1<<i)|xr[tar]) == xr[tar]) {
if (tri->sons[0])
find(tri->sons[0],i-1);
else
find(tri->sons[1],i-1);
}
else {
if (tri->sons[1])
find(tri->sons[1],i-1);
else
find(tri->sons[0],i-1);
}
}
}
int main() {
int n,i,k;
mx=-1;
ifstream in("xormax.in");
ofstream out("xormax.out");
in>>n;
add(root,20);
for (i=1; i<=n; i++) {
tar=i;
in>>k;
xr[i] = xr[i-1]^k;
find(root,20);
add(root,20);
}
out<<mx<<' '<<in1<<' '<<in2;
out.close();
return 0;
}