Pagini recente » Cod sursa (job #439933) | Cod sursa (job #640349) | Cod sursa (job #2263288) | Cod sursa (job #3347428) | Cod sursa (job #3350834)
#include <fstream>
#include <vector>
#include <unordered_map>
#define fr first
#define sc second
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
const int NRB=20;
int n;
unordered_map<int, int> poz;
vector<pair<int, int>> tr;
void add_node(int i, int val)
{
int u=0;
for(int b=NRB;b>=0;b--)
if((val&(1<<b))==0)
{
if(tr[u].fr==-1)
{
tr[u].fr=tr.size();
tr.push_back({-1, -1});
}
u=tr[u].fr;
}
else
{
if(tr[u].sc==-1)
{
tr[u].sc=tr.size();
tr.push_back({-1, -1});
}
u=tr[u].sc;
}
poz[u]=i;
}
pair<int, int> find_max(int val)
{
int u=0, v, ans=0;
for(int b=NRB;b>=0;b--)
{
v=u;
if((val&(1<<b))==0)
u=(tr[u].sc==-1)?tr[u].fr:tr[u].sc;
else
u=(tr[u].fr==-1)?tr[u].sc:tr[u].fr;
if(u==tr[v].sc)
ans^=(1<<b);
}
return {ans, poz[u]};
}
int main()
{
tr.push_back({-1, -1});
in>>n;
int xr=0, v, ans=-1, ansi=-1, ansj=-1;
for(int i=1;i<=n;i++)
{
add_node(i, xr);
in>>v; xr^=v;
auto pans=find_max(xr);
if((pans.fr^xr)>ans)
{
ans=pans.fr^xr;
ansi=i;
ansj=pans.sc;
}
}
out<<ans<<" "<<ansj<<" "<<ansi;
return 0;
}