Cod sursa(job #3253713)

Utilizator laura2020Moldovan Laura laura2020 Data 4 noiembrie 2024 15:39:52
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");
#define dim 2
#define NrBiti 20
struct raspuns
{
    int val,start,stop;
};
struct Trie
{
    int cnt,poz;
    Trie* v[dim];
    Trie()
    {
        cnt=poz=0;
        for(int i=0;i<dim;i++)
            v[i]=NULL;
    }
};
void adauga(Trie *nod,int sum,int poz,int PozBit)
{
    if(PozBit==-1)
    {
        nod->poz=poz;
        return ;
    }
    int bit=(sum&(1<<PozBit));
    if(bit>0)
        bit=1;
    if(nod->v[bit]==NULL)
    {
        nod->v[bit]=new Trie;
    }
    adauga(nod->v[bit],sum,poz,PozBit-1);
}
int ans;
int query(Trie *nod,int s,int pozBit)
{
    if(pozBit==-1)
    {
        return nod->poz;
    }
    bool bit=1-(s&(1<<pozBit)); ///bit opus
    if(nod->v[bit]==NULL) ///Nu am gasit bit opus
    {
        if(nod->v[1-bit]!=NULL)
            return query(nod->v[1-bit],s,pozBit-1);
        else
            return 0;
    }
    else ///Am gasit
    {
        ans|=(1<<pozBit);
        return query(nod->v[bit],s,pozBit-1);
    }
}

int main()
{
    Trie *root=new Trie;
    int n,i,nr,sum;
    raspuns maxi,aux;
    string s;
    fin>>n;
    sum=maxi.val=maxi.start=maxi.stop=0;
    for(i=1;i<=n;i++)
    {
        fin>>nr;
        sum^=nr;
        //cout<<sum<<" ";
        ans=0;
        aux.start=query(root,sum,NrBiti);
        aux.stop=i;
        aux.val=ans^sum;
        if(maxi.val<aux.val)
        {
            maxi=aux;
        }
        else if(maxi.val==aux.val)
        {
            if(maxi.stop>aux.stop)
            {
                maxi=aux;
            }
            else if(maxi.stop==aux.stop && maxi.stop-maxi.start>aux.stop-aux.start)
            {
                maxi=aux;
            }
        }
        adauga(root,sum,i,NrBiti);
    }
    fout<<maxi.val<<" "<<maxi.start+1<<" "<<maxi.stop;
    return 0;
}