Cod sursa(job #2739585)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 8 aprilie 2021 21:03:30
Problema Xor Max Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
//Ilie Dumitru
#include<cstdio>

struct trie
{
    int val, begin, end;
    trie *next[2];
};

trie* newTrie()
{
    trie *t=new trie;
    t->begin=1e7;
    t->end=-1;
    t->val=0;
    t->next[0]=t->next[1]=0;
    return t;
}

void insert(trie *t, int xor_val, int begin, int end)
{
    for(int i=20;i>-1;--i)
    {
        if(!t->next[(xor_val>>i) & 1])
            t->next[(xor_val>>i) & 1]=newTrie();
        t=t->next[(xor_val>>i) & 1];
    }
    t->val=xor_val;
    if(end>t->end || (end==t->end && begin>t->begin))
    {
        t->begin=begin;
        t->end=end;
    }
}

void query(trie *t, int xor_val, int& max, int& end)
{
    bool x;
    int i;
    for(i=20;i>-1;--i)
    {
        x=(xor_val>>i) & 1;
        if(t->next[!x])
            t=t->next[!x];
        else
            t=t->next[x];
    }
    max=t->val^xor_val;
    end=t->end;
}

int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    int N, x, i, xor_val=0, max=0, begin=0, end=0, aux1, aux2;
    trie *t=newTrie();
    insert(t, 0, 0, 0);
    scanf("%d", &N);
    for(i=0;i<N;++i)
    {
        scanf("%d", &x);
        xor_val^=x;
        insert(t, xor_val, 1, i+1);
        query(t, xor_val, aux1, aux2);
        if(aux1>max)
        {
            max=aux1;
            begin=aux2+1;
            end=i+1;
        }
    }
    fclose(stdin);
    printf("%d %d %d", max, begin, end);
    fclose(stdout);
    return 0;
}