Cod sursa(job #2589180)

Utilizator Tudor_PascaTudor Pasca Tudor_Pasca Data 25 martie 2020 21:27:25
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

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

int n, sum;
int v[100010];

struct trie
{
    int poz;
    trie *next[2];

    trie()
    {
        poz = 0;
        next[0] = nullptr;
        next[1] = nullptr;
    }
};

trie *T = new trie;

void ins(trie *node, int bit, int val, int i)
{
    if(bit == 0)
    {
        node -> poz = i;

        return;
    }

    bool x = val & (1 << bit);

    if(x == false)
    {
        if(node -> next[0] == nullptr)
            node -> next[0] = new trie;

        ins(node -> next[0], bit - 1, val, i);
    }
    else
    {
        if(node -> next[1] == nullptr)
            node -> next[1] = new trie;

        ins(node -> next[1], bit - 1, val, i);
    }
}

int query(trie *node, int bit, int val)
{
    if(bit == 0)
    {
        //cout << val << ' ' << node -> poz << '\n';

        return node -> poz;

        //cout << '\n';
    }

    bool x = val & (1 << bit);

    //cout << x << ' ';

    if(x == 0)
    {
        if(node -> next[1] != nullptr)
            return query(node -> next[1], bit - 1, val);
        else
            return query(node -> next[0], bit - 1, val);
    }
    else
    {
        if (node -> next[0] != nullptr)
            return query(node -> next[0], bit - 1, val);
        else
            return query(node -> next[1], bit - 1, val);
    }
}

int main()
{
    in >> n;

    for(int i = 1; i <= n; i++)
    {
        int x;

        in >> x;

        v[i] = x ^ v[i-1];
    }

    pair<int, pair<int, int>> rez;
    rez.first = -1;

    ins(T, 21, 0, 0);

    for(int i = 1; i <= n; i++)
    {
        int aux = query(T, 21, v[i]);

        //cout << i << ' ' << aux << ' ' << v[i] << ' ' << (aux ^ v[i]) << "\n";

        if((v[i] ^ v[aux]) > rez.first)
        {
            rez.first = v[i] ^ v[aux];
            rez.second.first = aux;
            rez.second.second = i;
        }

        //cout << rez.first << "\n\n\n";

        ins(T, 21, v[i], i);
    }

    out << rez.first << ' ' << rez.second.first + 1 << ' ' << rez.second.second << '\n';

    return 0;
}