Pagini recente » Cod sursa (job #3295059) | Cod sursa (job #591037)
Cod sursa(job #591037)
#include <cstdio>
#include <vector>
using namespace std;
#define l 20
vector <vector <pair <int, int> > > v;
vector <int> trie;
int n, sol, r1, r2;
int getNext(int root, int c)
{
int i;
for (i=0; i<v[root].size(); i++)
if (v[root][i].first==c) return v[root][i].second;
return -1;
}
void addTrie(int x, int p)
{
int i, c, root=0, next;
for (i=l; i>=0; i--)
{
c=x&(1<<i);
if (c>0) c=1;
next=getNext(root, c);
if (next==-1)
{
next=trie.size();
trie.push_back(p);
v.resize(trie.size());
v[root].push_back(make_pair(c, next));
} else trie[next]=p;
root=next;
}
}
void search(int x, int p)
{
int i, c, root=0, next, sum=0;
for (i=l; i>=0; i--)
{
c=x&(1<<i);
if (c>0) c=1;
c=!c;
next=getNext(root, c);
if (next==-1)
{
c=!c;
next=getNext(root, c);
} else sum+=(1<<i);
root=next;
}
if (sum>sol)
{
sol=sum;
r1=trie[root]+1;
r2=p;
}
}
int main()
{
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%d", &n);
int i, x, s=0;
trie.resize(1);
v.resize(1);
for (i=1; i<=n; i++)
{
scanf("%d", &x);
s^=x;
if (i>1) search(s, i);
addTrie(s, i);
}
printf("%d %d %d\n",sol, r1, r2);
}