Pagini recente » Cod sursa (job #348896) | Cod sursa (job #436012) | Cod sursa (job #1378256) | Cod sursa (job #979998) | Cod sursa (job #643850)
Cod sursa(job #643850)
#include <fstream>
#include <iostream>
using namespace std;
const int D = 21,N=100005;
int v[N];
struct Trie {
Trie *st, *dr;
int poz;
Trie() {
st = dr = NULL;
}
};
Trie *trie = new Trie();
ifstream in("xormax.in");
ofstream out("xormax.out");
inline bool bit(int x,int p)
{
return (x & (1<<p))!=0;
}
void push(Trie *trie,int val,int poz)
{
for (int p=D-1;p>=0;p--)
if (bit(val,p))
{
if ((*trie).dr==NULL)
(*trie).dr=new Trie();
trie=(*trie).dr;
}
else
{
if ((*trie).st==NULL)
(*trie).st=new Trie();
trie=(*trie).st;
}
(*trie).poz=poz;
}
// (*trie).st
// trie->st
int search(Trie *trie,int val)
{
for (int p=D-1;p>=0;p--)
if (bit(val,p))
if ((*trie).st!=NULL)
trie=(*trie).st;
else
trie=(*trie).dr;
else
if ((*trie).dr!=NULL)
trie=(*trie).dr;
else
trie=(*trie).st;
return (*trie).poz;
}
int main()
{
int n,x,st=0,dr=0;
push(trie,0,0);
in>>n;
for (int i=1;i<=n;i++)
{
in>>v[i];
v[i]^=v[i-1];
push(trie,v[i],i);
x=search(trie,v[i]);
if ((v[dr]^v[st])<(v[i]^v[x]))
{
st=x;
dr=i;
}
}
out<<(v[dr]^v[st])<<" "<<st+1<<" "<<dr<<"\n";
return 0;
}