Cod sursa(job #3147925)

Utilizator Simon2712Simon Slanina Simon2712 Data 28 august 2023 09:32:09
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 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;
    int fiu[2]={-1,-1};
} v[VAL_MAX+1];
int vxor[N];
int st,dr=1;
int cnt=0;
void caut(int nod,int poz,int bit)
{
    if(bit==-1)
    {
        if((vxor[poz]^vxor[v[nod].last])>(vxor[dr]^vxor[st]))
        {
            dr=poz;
            st=v[nod].last;
        }
        return;
    }
    int p=1;
    if((vxor[poz]&(1<<bit)))
        p=0;
    if(v[nod].fiu[p]==-1)
        caut(v[nod].fiu[1-p],poz,bit-1);
    else
        caut(v[nod].fiu[p],poz,bit-1);
}
void add(int nod,int poz,int bit)
{
    if(bit==-1)
    {
        v[nod].last=poz;
        return;
    }
    int p=0;
    if((vxor[poz]&(1<<bit)))
        p=1;
    if(v[nod].fiu[p]==-1){
        cnt++;
        v[nod].fiu[p]=cnt;
    }
    add(v[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(0,0,20);
    for(i=1;i<=n;i++){
        caut(0,i,20);
        add(0,i,20);
    }
    fout<<(vxor[dr]^vxor[st])<<" "<<st+1<<" "<<dr;
    return 0;
}