Cod sursa(job #1866523)

Utilizator mirupetPetcan Miruna mirupet Data 3 februarie 2017 11:18:23
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include<cstdio>
using namespace std;

FILE *fin = freopen("xormax.in", "r", stdin);
FILE *fout = freopen("xormax.out", "w", stdout);

const int NMax = 100010;
int N, left, right, sol, Max, Maxx, nr;
int v[NMax];

struct Trie
{
    Trie *son[2];
    int ind;

    Trie()
    {
        son[0] = son[1] = 0;
        ind = 0;
    }
};
Trie *root;

void Insert(Trie *root, int bit, int val, int ind)
{
    if (bit == -1)
    {
        root -> ind = ind;
        return;
    }

    if (((val >> bit) & 1) == 0)
    {
        if (root -> son[0] == NULL) root -> son[0] = new Trie;
        Insert(root -> son[0], bit - 1, val, ind);
    }
    else
    {
        if (root -> son[1] == NULL) root -> son[1] = new Trie;
        Insert(root -> son[1], bit - 1, val, ind);
    }
}

void Search(Trie *root, int bit, int val)
{
    if (bit == -1)
    {
        sol = root -> ind;
        return;
    }

    int bval = ((val >> bit) & 1);
    if (root -> son[1 - bval] != 0)  Search(root -> son[1 - bval], bit - 1, val);
    else                             Search(root -> son[bval], bit - 1, val);
}

int main()
    {
        scanf("%d", &N);

        scanf("%d", &v[1]);
        Max = -1;
        for (int i = 2, X; i <= N; i++)
        {
            scanf("%d", &X);
            v[i] = v[i - 1] ^ X;
            if (Maxx < X)   Maxx = X;
        }


        while (Maxx){nr++; Maxx /= 2;}

        root = new Trie;
        Insert(root, nr, 0, 0);

        for (int i = 1; i <= N; i++)
        {
            Search(root, nr, v[i]);
            if ((v[i] ^ v[sol]) > Max)
            {
                Max = (v[i] ^ v[sol]);
                left = sol + 1;
                right = i;
            }

            Insert(root, nr, v[i], i);
        }

        printf("%d %d %d\n", Max, left, right);
    }