Cod sursa(job #2282632)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 14 noiembrie 2018 10:47:58
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int NMAX = 100005;
int v[NMAX];
int p[25],s[25],ma=0,x,y,n;

struct trie{
trie *bit[2];
int numar;
trie()
{
    numar = 0;
    bit[1] = bit[0] = NULL;
}
};

trie *radacina = new trie;

void adauga(trie *&nod,int i,int dr)
{
    if(i == 22)
    {
        nod->numar = dr;
        return;
    }
    if(nod->bit[s[i]] == NULL)
        nod->bit[s[i]] = new trie;
    adauga(nod->bit[s[i]],i+1,dr);
}

void putInS(int x)
{
    memset(s,0,sizeof(s));
    int k = -1;
    while(x)
    {
        s[++k] = (x&1);
        x >>= 1;
    }
    for (int i = 0; i <= 10; i++)
        swap (s[i],s[21-i]);
}

int cauta(trie *&nod,int i)
{
    if(i == 22)
    {
        y = nod->numar;
        return 0;
    }
    if(nod->bit[1-s[i]]!=NULL)
        return p[(21-i)]+cauta(nod->bit[1-s[i]],i+1);
    else
        return cauta(nod->bit[s[i]],i+1);
}

int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; i++)
        scanf("%d",&v[i]);
    for(int i = 1 ; i <= n ; i++)
        v[i] = v[i] ^ v[i-1];
    p[0] = 1;
    for(int i = 1 ; i <= 22 ; i++)
        p[i] = (p[i-1]<<1);
    ma = 0;
    int num;
    putInS(0);
    adauga(radacina,0,0);
    int stm,drm;
    stm = drm = 1;
    for(int i = 1 ; i <= n ; i++)
    {
        putInS(v[i]);
        num = cauta(radacina,0);
        if(num > ma)
        {
            ma = num;
            stm = y;
            drm = i;
        }
        adauga(radacina,0,i);
    }
    printf("%d %d %d\n",ma,stm+1,drm);
    return 0;
}