Cod sursa(job #1942590)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 28 martie 2017 08:54:16
Problema Xor Max Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <bits/stdc++.h>

#define maxBits 20
#define Nmax 100002

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

struct Trie
{
    int idx;
    Trie *next[2];
};
Trie *Root;

int N;
int i;
int A[Nmax];
int mx = -1, start, finish;

void insert(int idx)
{
    Trie *P = Root;
    for(int i = maxBits; i >= 0; i--)
    {
        int b = ((A[idx] & (1 << i)) != 0);
        if(P -> next[b] == NULL)
        {
            P -> next[b] = new Trie;
            P = P -> next[b];
            P -> idx = 0;
            P -> next[0] = NULL;
            P -> next[1] = NULL;
        }
        else P = P -> next[b];
    }
    P -> idx = max(P -> idx, idx);
}

int getIndex(int V)
{
    Trie *P = Root;
    for(int i = maxBits; i >= 0; i--)
    {
        int b = ((V & (1 << i)) != 0);
        if(P -> next[!b] != NULL)
            P = P -> next[!b];
        else P = P -> next[b];
    }
    return P -> idx;
}

int main()
{
    Root = new Trie;
    Root -> next[0] = NULL;
    Root -> next[1] = NULL;
    fin >> N;
    for(i = 1; i <= N; i++)
    {
        fin >> A[i];
        A[i] ^= A[i - 1];
        if(mx < A[i])
        {
            mx = A[i];
            start = 1;
            finish = i;
        }
        insert(i);
        int pos = getIndex(A[i]);
        if(mx < (A[i] ^ A[pos]))
        {
            mx = A[i] ^ A[pos];
            start = pos;
            finish = i;
        }
    }
    fout << mx << " " << start + 1 << " " << finish << "\n";
    return 0;
}