Pagini recente » Diferente pentru utilizator/razzor intre reviziile 3 si 2 | Diferente pentru utilizator/xtreme77_ericpts_stefex09 intre reviziile 4 si 3 | Istoria paginii runda/algoritmul_lee | Diferente pentru problema/aby intre reviziile 16 si 15 | Cod sursa (job #2968045)
///Alexandru Morus
#include <bits/stdc++.h>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
int poz1,poz2,afs;
struct TrieNode
{
int frg;
TrieNode *nxt[2];
TrieNode()
{
this->frg = -1;
memset(this->nxt,0,sizeof(this->nxt));
}
};
TrieNode * root = new TrieNode;
void ins(TrieNode * root, int N,int pos)
{
TrieNode *curr = root;
for(int bit = 20; bit >= 0; bit--)
{
bool now = (N & (1 << bit));
if(curr->nxt[now] == NULL)
{
curr->nxt[now] = new TrieNode;
}
curr = curr->nxt[now];
}
if(curr->frg == -1)
{
curr->frg = pos;
}
}
void lookup(TrieNode * root, int N, int pos)
{
TrieNode *curr = root;
afs = 0;
for(int bit = 20; bit >= 0; bit--)
{
int now = (N & (1 << bit));
if(curr->nxt[!now] == NULL)
{
curr = curr -> nxt[now];
}
else
{
curr = curr -> nxt[!now];
afs |= (1 << bit);
}
}
poz1 = pos;
poz2 = curr -> frg;
}
int main ()
{
int i,t,n,j,q,x = 0,a,afs1 = 0,poz1denis,poz2denis;
in >> n;
ins(root, 0, 0);
for(i = 1; i <= n; i ++)
{
in >> a;
x = x ^ a;
ins(root,x,i);
lookup(root,x,i);
if(afs1 < afs)
{
afs1 = afs;
poz1denis = poz1;
poz2denis = poz2;
}
}
out << afs1 << ' ' << poz1denis << ' ' << poz2denis;
return 0;
}