Cod sursa(job #1878618)

Utilizator silkMarin Dragos silk Data 14 februarie 2017 12:14:38
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <bits/stdc++.h>
#define NMax 100000
using namespace std;

struct trie{
    int idx;
    trie* leg[2];
    void Init()
    {
        leg[0] = leg[1] = NULL;
    }
};

trie *rad = new trie;
char s[24];
int sum[NMax+1];
int v[NMax+1];
int id;

void Insert(char* s)
{
    int i,j;
    trie *q, *p = rad;
    for(i = 0; s[i]; ++i)
    {
        j = s[i]-'0';
        if(!p->leg[j]){
            q = new trie;
            q->Init();
            p->leg[j] = q;
        }
        p = p->leg[j];
    }
    p->idx = id;
}

int Search(char* s)
{
    int i,j;
    trie *p = rad;
    for(i = 0; s[i]; ++i)
    {
        j = !(s[i]-'0');
        if(p->leg[j]) p = p->leg[j];
        else p = p->leg[!j];
    }
    return p->idx;
}

int main(){
    FILE* fin = fopen("xormax.in","r");
    FILE* fout = fopen("xormax.out","w");

    int i,j,N,p,bit,res,inc,sf,vmax=0;

    rad->Init();
    fscanf(fin,"%d",&N);
    for(i = 1; i <= N; ++i)
    {
        fscanf(fin,"%d",&v[i]);
        vmax = max(vmax, v[i]);
    }

    for(bit = 20; bit && !(vmax & (1<<bit)); --bit);
    for(i = 0; i <= bit; ++i) s[i] = '0';
    Insert(s);

    for(res = -1, i = 1; i <= N; ++i)
    {
        sum[i] = sum[i-1] ^ v[i];
        for(j = bit; j >= 0; --j)
        if(sum[i] & (1<<j)) s[bit-j] = '1';
        else s[bit-j] = '0';

        id = i;
        Insert(s);
        p = Search(s);
        if((sum[i]^sum[p]) > res)
        {
            res = sum[i] ^ sum[p];
            inc = p+1;
            sf = i;
        }
    }

    fprintf(fout,"%d %d %d\n",res,inc,sf);


return 0;
}