Cod sursa(job #2888750)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 11 aprilie 2022 20:05:26
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
//Ilie Dmitru
#include<fstream>
#include<cstdio>
typedef long long int ll;
const int NMAX=100005;
const ll MOD=194767;

FILE* f=fopen("xormax.in", "r"), *g=fopen("xormax.out", "w");

int trie[NMAX*21][2], trieCnt, triePos[NMAX*21];
int MAXBIT;

void push(int x, int pos)
{
    int i, val, index=0;
    for(i=MAXBIT;i>-1;--i)
    {
        val=(x>>i)&1;
        if(!trie[index][val])
            trie[index][val]=++trieCnt;
        index=trie[index][val];
    }
    triePos[index]=pos;
}

int findMax(int x, int& startPos)
{
    int i, val, res=0, index=0;
    for(i=MAXBIT;i>-1;--i)
    {
        val=!((x>>i)&1);
        if(trie[index][val])
        {
            res|=1<<i;
            index=trie[index][val];
        }
        else
            index=trie[index][!val];
    }
    startPos=triePos[index];
    return res;
}

int v[NMAX];

int main()
{
    int i, N, x=0, r, ans=0, pos, bestStart=-1, bestEnd=0, maxX=0;
    fscanf(f, "%d", &N);
    for(i=0;i<N;++i)
    {
        fscanf(f, "%d", v+i);
        if(maxX<v[i])
            maxX=v[i];
    }
    while(maxX)
        maxX>>=1, ++MAXBIT;
    push(0, -1);
    x=0;
    for(i=0;i<N;++i)
    {
        x^=v[i];
        r=findMax(x, pos);
        push(x, i);
        if(r>ans)
        {
            ans=r;
            bestStart=pos;
            bestEnd=i;
        }
    }
    fprintf(g, "%d %d %d", ans, bestStart+2, bestEnd+1);
    fclose(f);
    fclose(g);
    return 0;
}