Cod sursa(job #3349468)

Utilizator cezarinfoTulceanu Cezar cezarinfo Data 29 martie 2026 22:15:22
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.82 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
const int NMAX=100007,BITS=21;
int n;
int v[NMAX];
int sp[NMAX];
int l,r,maxx;//vrem r min
struct node{
    int val;
    vector<int> ind;
    node *zero,*one;
    node(){
        val=0;
        ind.clear();
        zero=nullptr;
        one=nullptr;
    };
};
node* root=new node();
void add(int x,int idx){
    int b=1<<(BITS-1);
    node* nod=root;
    while(b>0)
    {
        int dif=int(int(x)&int(b));
        if(dif==0)
        {
            if(nod->zero==nullptr)
            {
                nod->zero=new node();
            }
            nod=nod->zero;
        }
        else
        {
            if(nod->one==nullptr)
            {
                nod->one=new node();
            }
            nod=nod->one;
        }
        b=b>>1;
    }
    nod->val++;
    nod->ind.push_back(idx);
}
//gasim cel mai apropiat de x, cu cel mai mare indice mai mic sau egal cu pos
struct per{
    int val,ind;
};
per el;
per fin(int x,int pos)
{
    int b=1<<(BITS-1);
    node* nod=root;
    int valoare=0;
    while(b>0)
    {
        int dif=int(int(x)&int(b));
        if(dif==0)
        {
            if(nod->zero==nullptr)
            {
                valoare+=b;
                nod=nod->one;
            }
            else
            {
                nod=nod->zero;
            }
        }
        else
        {
            if(nod->one==nullptr)
            {
                nod=nod->zero;
            }
            else
            {
                valoare+=b;
                nod=nod->one;
            }
        }
        b=b>>1;
    }
    //avEM VECTORUL nod->id
    //Vrem nodul
    vector<int>*ad=&(nod->ind);
    int st=0,dr=ad->size()-1;
    int ras=-1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if((*ad)[mij]<=pos)
        {
            ras=mij;
            st=mij+1;
        }
        else
        {
            dr=mij-1;
        }
    }
    if(ras!=-1)
    {
        el.ind=(*ad)[ras];
    }
    else
    {
        el.ind=-1;
    }
    el.val=valoare;
    return el;
}
int main()
{
    in>>n;
    add(0,0);
    for(int i=1;i<=n;i++)
    {
        in>>v[i];
        sp[i]=int(sp[i-1])^int(v[i]);
        add(sp[i],i);
    }
    int opos=(1<<BITS)-1;
    for(int i=1;i<=n;i++)
    {
        per epic=fin(opos-sp[i],i-1);
        epic.val=int(epic.val)^int(sp[i]);
        if(epic.ind!=-1)
        {
            if(epic.val>maxx)
            {
                maxx=epic.val;
                l=epic.ind+1;
                r=i;
            }
        }
    }
    if(maxx==0)
    {
        out<<0<<" "<<1<<" "<<1;
        return 0;
    }
    out<<maxx<<" "<<l<<" "<<r;
}