Cod sursa(job #3209274)
Utilizator | Benchea Matei matei__b | Data | 2 martie 2024 11:19:39 |
---|---|---|---|
Problema | Xor Max | Scor | 20 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 3.15 kb |
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define chad char
#define mod 1'000'000'009
#define dim 100005
#define lim 1000000
#define INF 1000000000
#define FOR(i,a,b) for(int i=(a); i<=(b); i++)
#define piii pair<int,pair<int,int> >
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define nr_biti __builtin_popcount
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
bool curr[dim];
struct trie
{
struct nod
{
vector<int> pos;
nod *st;
nod *dr; // merg in stanga cu 1 si in dreapta cu 0
nod()
{
st=dr=nullptr;
}
};
nod *rad=new nod;
void insert(int x,int ind)
{
nod *aux=rad;
for(int i=29; i>=0; i--)
{
if(x&(1<<i))
{
//cout << 1;
if(aux->st==nullptr)
{
aux->st=new nod;
aux=aux->st;
}
else
{
aux=aux->st;
}
}
else
{
//cout << 0;
if(aux->dr==nullptr)
{
aux->dr=new nod;
aux=aux->dr;
}
else
{
aux=aux->dr;
}
}
if(i==0)
aux->pos.pb(ind);
}
}
pii cauta(int x)
{
nod *aux=rad;
int ans=0;
for(int i=29; i>=0; i--)
{
if(x&(1<<i))
{
if(aux->dr!=nullptr)
{
ans|=(1<<i);
aux=aux->dr;
}
else
{
aux=aux->st;
}
}
else
{
if(aux->st!=nullptr)
{
ans|=(1<<i);
aux=aux->st;
}
else
{
aux=aux->dr;
}
}
if(i==0)
{
int mx=0;
for(auto it:aux->pos)
mx=max(mx,it);
return mp(ans,mx);
}
}
}
}v;
int n;
int a[dim];
int sp;
int mx,st,dr=1e9;
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(nullptr);
fout.tie(nullptr);
fin >> n;
for(int i=1; i<=n; i++)
{
fin >> a[i];
sp=(sp^a[i]);
v.insert(sp,i);
pii u=v.cauta(sp);
if(u.first>mx)
{
mx=u.first;
dr=i;
st=u.second;
}
else if(u.first==mx && i-u.second+1<dr-st+1)
{
mx=u.first;
dr=i;
st=u.second;
}
}
fout << mx << " " << st+1 << " " << dr;
return 0;
}