Cod sursa(job #2585174)

Utilizator AlexandruGabrielAliciuc Alexandru AlexandruGabriel Data 18 martie 2020 18:41:59
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <bits/stdc++.h>
#define N 100005

using namespace std;

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

struct Trie
{
    int pos;
    Trie *fiu[2];

    Trie()
    {
        pos = 0;
        fiu[0] = fiu[1] = NULL;
    }
};

Trie *t = new Trie;
int n, x, a[N], k;
int val, valPos;
int st, dr, ans;

int highestBit(int x)
{
    int maxim = 0;
    for (int i = 0; i < 21; i++)
        if ((1 << i) & x)
            maxim = i;
    return maxim;
}

void Insert(Trie *p, int currK, int x, int ind)
{
    if (currK == -1)
        p -> pos = ind;
    else
    {
        bool bit = 0;
        if (x & (1 << currK))
            bit = 1;

        if (p -> fiu[bit] == NULL)
            p -> fiu[bit] = new Trie;

        Insert(p -> fiu[bit], currK - 1, x, ind);
    }
}

void Search(Trie *p, int currK, int x)
{
    if (currK == -1)
        valPos = p -> pos;
    else
    {
        bool bit = 0;
        if (x & (1 << currK))
            bit = 1;

        if (p -> fiu[!bit] != NULL)
        {
            val ^= (1 << currK);
            Search(p -> fiu[!bit], currK - 1, x);
        }
        else
            Search(p -> fiu[bit], currK - 1, x);
    }
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        fin >> x;
        a[i] = (x ^ a[i - 1]);
        k = max(k, highestBit(a[i]));
    }

    Insert(t, k, 0, 0);
    for (int i = 1; i <= n; i++)
    {
        val = valPos = 0;
        Search(t, k, a[i]);

        if (val > ans)
        {
            ans = val;
            st = valPos + 1;
            dr = i;
        }

        Insert(t, k, a[i], i);
    }

    fout << ans << " " << st << " " << dr;
    return 0;
}