Cod sursa(job #2488058)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 6 noiembrie 2019 07:00:38
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;

struct Node
{
    int number;
    Node* v[2] = {nullptr, nullptr};
} *trie = new Node;

void push_trie(int x)
{
    Node* temp = trie;

    for(int i = 20; i >=0; --i)
    {
        bool bit = (x & (1 << i));

        if(!temp->v[bit])
            temp->v[bit] = new Node;

        temp = temp->v[bit];
    }


    temp->number = x;
}

int max_trie(int x)
{

    Node* temp = trie;

    for(int i = 20; i >= 0; --i)
    {
        bool bit = (x & (1 << i));

        if(temp->v[!bit])
            temp = temp->v[!bit];
        else
            temp = temp->v[bit];
    }

    return x ^ temp->number;
}

int v[100001], N;

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

int main()
{
    fin >> N;

    int MAX = 0;
    int stop = 1;
    int start = 1;

    for(int i = 1; i <= N; ++i)
    {
        fin >> v[i];
        v[i] ^= v[i - 1];

        push_trie(v[i]);

        int current = max_trie(v[i]);

        if(current > MAX)
        {
             MAX = current;
             stop = i;
        }
    }


    for(int i = stop; i > 0 && (v[stop] ^ v[i]) != MAX; --i)
        start = i;

    fout << MAX << " " << start << " " << stop;
}