Cod sursa(job #2747155)

Utilizator valentinchipuc123Valentin Chipuc valentinchipuc123 Data 28 aprilie 2021 21:08:11
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

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

struct trie
{
    int index;
    trie* fiu[2];

    trie()
    {
        index = -1;
        fiu[0] = nullptr;
        fiu[1] = nullptr;
    }
};

trie *T = new trie;
int n;
int v[100100];
pair<int, pair<int, int>> ans = {-1, {-1, -1}};

void ins(trie *node, int bit, int val, int i)
{
    if(bit == 0)
    {
        //cout << "debug\n";

        node -> index = i;
        return;
    }

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

    //cout << bit << ' ' << x << '\n';

    if(x == 0)
    {
        if(node -> fiu[0] == nullptr)
        {
            //cout << "new\n";
            node -> fiu[0] = new trie;
            //cout << "new finished\n";
        }

        //cout << "0 going down\n";

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

        //cout << "1 going down\n";

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

int query(trie *node, int bit, int val)
{
    if(bit == 0)
        return node -> index;

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

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

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

        return query(node -> fiu[0], bit - 1, val);
    }
}

int main()
{
    in >> n;

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

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

    //cout << "warmup\n";

    ins(T, 20, 0, 0);

    //cout << "START\n";

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

        if((v[x] ^ v[i]) > ans.first)
        {
            ans.first = (v[x] ^ v[i]);
            ans.second = make_pair(x + 1, i);
        }

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

    out << ans.first << ' ' << ans.second.first << ' ' << ans.second.second << '\n';

    return 0;
}