Pagini recente » Cod sursa (job #2455137) | Cod sursa (job #1884274) | Cod sursa (job #810959) | Cod sursa (job #2039927) | Cod sursa (job #948870)
Cod sursa(job #948870)
//sumxor[i]=a[1]^a[2]^a[3]^...^a[i]
//introducem in trie bitii unei sume xor
//incepand cu cel mai semnificativ si retinand pozitia
//sumxor[i]^sumxor[j-1] = a[j]^a[j+1]^...^a[i]
#include <fstream>
#define In "xormax.in"
#define Out "xormax.out"
#define Nmax 100010
#define maxb 22
using namespace std;
int sumxor[Nmax];
struct Trie
{
int poz;
Trie *b[2];
Trie()
{
poz = 0;
b[0] = b[1] = 0;
}
};
Trie *T = new Trie;
//introducem suma xor x in trie incepand cu bitul cel mai semnificativ
inline void Adauga(Trie *nod, int x,int poz)
{
int i;
bool bit;
for(i = maxb;i >= 0;i--)
{
bit = (x & (1<<i));//valoarea bitului de pe pozitia i
if(nod->b[bit]==0)
nod->b[bit] = new Trie;
nod = nod ->b[bit];
}
nod -> poz = poz;
}
//cautam in trie o pozitia care ar face suma xor maxima
inline int Cauta(Trie *nod,int x)
{
int i;
bool bit;
for(i = maxb;i >= 0 ;i--)
{
bit = (x&(1<<i));
if(nod->b[!bit]!=0)//caut bitul opus pentru a maximiza suma xor
nod = nod->b[!bit];
else
nod = nod->b[bit];
}
return nod -> poz;
}
int main()
{
int i, N, x,j,sol = -1,st,dr;
ifstream f(In);
f >> N;
Adauga(T,0,0);
for(i = 1;i <= N ; i++)
{
f >> x;
sumxor[i] = (sumxor[i-1]^x);
j = Cauta(T,sumxor[i]);
if(sol < (sumxor[i] ^ sumxor[j]))
{
sol = sumxor[i] ^ sumxor[j];
st = j+1;
dr = i;
}
Adauga(T,sumxor[i],i);
}
f.close();
ofstream g(Out);
g<<sol<<" "<<st<<" "<<dr<<"\n";
g.close();
return 0;
}