Pagini recente » Cod sursa (job #3289494) | Cod sursa (job #1977126) | Cod sursa (job #3198388) | Cod sursa (job #945202) | Cod sursa (job #3245350)
#include <bits/stdc++.h>
const std :: string FILENAME = "xormax";
std :: ifstream f(FILENAME + ".in");
std :: ofstream g(FILENAME + ".out");
const int NMAX = 1e5 + 5;
struct nod
{
int ind = -1;
nod * st = nullptr;
nod * dr = nullptr;
};
int n;
int start;
int stop;
int maxi = -1;
int i;
int csor[NMAX];
int v[NMAX];
std :: string s;
void add(nod * & trie, int poz)
{
if(poz < s.size())
{
if(s[poz] == '0')
{
if(trie -> st == nullptr)
{
trie -> st = new nod;
}
add(trie -> st, poz + 1);
}
else
{
if(trie -> dr == nullptr)
{
trie -> dr = new nod;
}
add(trie -> dr, poz + 1);
}
}
else
{
trie -> ind = i;
}
}
std :: string to_string(int x)
{
std :: string aux = "";
while(x)
{
if(x % 2)
{
aux += '1';
}
else
{
aux += '0';
}
x /= 2;
}
while(aux.size() < 21)
{
aux += '0';
}
std :: reverse(aux.begin(), aux.end());
return aux;
}
int op(nod * trie, int poz)
{
if(poz < s.size())
{
if(s[poz] == '0')
{
if(trie -> dr)
{
return op(trie -> dr, poz + 1);
}
else
{
return op(trie -> st, poz + 1);
}
}
else
{
if(trie -> st)
{
return op(trie -> st, poz + 1);
}
else
{
return op(trie -> dr, poz + 1);
}
}
}
else
{
return trie -> ind;
}
}
int main()
{
f >> n;
for(int i = 1; i <= n; i ++)
{
f >> v[i];
}
for(int i = 1; i <= 21; i ++)
{
s += '0';
}
nod * trie = new nod;
add(trie, 0);
for(i = 1; i <= n; i ++)
{
csor[i] = csor[i - 1] ^ v[i];
s = to_string(csor[i]);
int st = op(trie, 0);
if((csor[i] ^ csor[st]) > maxi)
{
start = st;
stop = i;
maxi = (csor[i] ^ csor[st]);
}
add(trie, 0);
}
g << maxi << " " << start + 1 << " " << stop;
return 0;
}