Cod sursa(job #2082733)

Utilizator maria_sinteaMaria Sintea maria_sintea Data 6 decembrie 2017 18:59:14
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include <cstdio>
#define N 100005

using namespace std;

int n, a[N], maxi=0, st, sf;
struct nod
{
    int nr;
    nod *cif[2];
    nod()
    {
        for(int i=0;i<=1;i++)
            cif[i]=NULL;
        nr=0;
    }
};

void adaug(nod *v, int n, int poz, int nmax)
{
    if(nmax==-1)
    {
          v->nr=poz;
          return;
    }
    bool nc=n&(1<<nmax);
    if(v->cif[nc]==NULL)
        v->cif[nc]=new nod();
    adaug(v->cif[nc], n, poz, nmax-1);
}

int cautare(nod *v, int nmax, int n)
{
    if(nmax==-1)
        return v->nr;
    bool nc=n&(1<<nmax);
    if(v->cif[!nc]==NULL)
        return cautare(v->cif[nc], nmax-1, n);
    return cautare(v->cif[!nc], nmax-1, n);
}

void citire()
{
    scanf("%d\n", &n);
    nod *r=new nod();
    adaug(r, 0, 0, 21);
    for(int i=1;i<=n;i++)
    {
        scanf("%d ", &a[i]);
        a[i]=a[i-1]^a[i];
        int poz=cautare(r, 21, a[i]);
        int nc=a[poz]^a[i];
        if(nc>maxi)
        {
            maxi=nc;
            st=poz+1;
            sf=i;
        }
        adaug(r, a[i], i, 21);
    }
}

int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);

    citire();
    printf("%d %d %d", maxi, st, sf);
    return 0;
}