Cod sursa(job #3148244)

Utilizator Simon2712Simon Slanina Simon2712 Data 30 august 2023 08:54:49
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int N=1e5+1;
const int VAL_MAX=(1<<21);
struct ura{
    int last=-1;
    ura *fiu[2]={NULL,NULL};
} v[VAL_MAX+1];
ura *root=new ura;
int vxor[N];
int st,dr=1;
void caut(ura *nod,int poz,int bit)
{
    if(bit==-1)
    {
        if((vxor[poz]^vxor[nod->last])>(vxor[dr]^vxor[st]))
        {
            dr=poz;
            st=nod->last;
        }
        return;
    }
    int p=1;
    if((vxor[poz]&(1<<bit)))
        p=0;
    if(nod->fiu[p]==NULL)
        caut(nod->fiu[1-p],poz,bit-1);
    else
        caut(nod->fiu[p],poz,bit-1);
}
void add(ura *nod,int poz,int bit)
{
    if(bit==-1)
    {
        nod->last=poz;
        return;
    }
    int p=0;
    if((vxor[poz]&(1<<bit)))
        p=1;
    if(nod->fiu[p]==NULL)
        nod->fiu[p]=new ura;
    add(nod->fiu[p],poz,bit-1);
}
int main()
{
    int n,i,a;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a;
        vxor[i]=(vxor[i-1]^a);
    }
    add(root,0,20);
    for(i=1;i<=n;i++){
        caut(root,i,20);
        add(root,i,20);
    }
    fout<<(vxor[dr]^vxor[st])<<" "<<st+1<<" "<<dr;
    return 0;
}