Cod sursa(job #2488056)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 6 noiembrie 2019 06:07:52
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 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)
{
    stack<bool> binary;

    int copy_x = x;

    for(int i = 1; i <= 22; ++i)
    {
        binary.push(x % 2);
        x = x/2;
    }
    cout << copy_x <<" ";
    Node* temp = trie;

    while(binary.empty() == false)
    {
        if(temp->v[binary.top()] == nullptr)
            temp->v[binary.top()] = new Node;

        temp = temp->v[binary.top()];

        cout << binary.top();
        binary.pop();
    }
cout << endl;
    temp->number = copy_x;
}

int max_trie(int x)
{
    stack<bool> binary;

    int copy_x = x;

    for(int i = 1; i <= 22; ++i)
    {
        binary.push(x % 2);
        x = x/2;
    }

    Node* temp = trie;

    while(binary.empty() == false)
    {
        if(temp->v[!binary.top()] == nullptr)
            temp = temp->v[binary.top()];
        else
            temp = temp->v[!binary.top()];

        binary.pop();
    }

    return copy_x ^ temp->number;
}

int v[100001], N;

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

int main()
{
    fin >> N;

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

        push_trie(v[i]);
    }



    int MAX = -1000000000;
    int stop = 0;
    int start = 0;

    for(int i = 1; i <= N; ++i)
    {
         int current = max_trie(v[i]);
         if(current >= MAX)
         {
             MAX = current;
             stop = i;
         }
    }


    int xorsum = 0;

    for(int i = stop; i > 0; --i)
    {
        xorsum ^= (v[i] ^ v[i - 1]);

        if(xorsum == MAX)
        {
            start = i;
            break;
        }
    }


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