Cod sursa(job #2773179)

Utilizator Edyci123Bicu Codrut Eduard Edyci123 Data 5 septembrie 2021 13:36:42
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <bits/stdc++.h>
#define DIM 100005

using namespace std;

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

struct trie
{
    int poz;
    trie* F[2];
    trie()
    {
        poz = 0;
        F[0] = F[1] = 0;
    }
};

trie * rad = new trie;
int n, x[DIM], maxi, pozStart, pozStop;

void inserare(trie * p, int ind, int k)
{
    if(k < 0)
    {
        p -> poz = ind;
        return ;
    }
    if(!p -> F[((x[ind] >> k) & 1)])
    {
        trie* t = new trie;
        p -> F[((x[ind] >> k) & 1)] = t;
    }
    inserare(p -> F[((x[ind] >> k) & 1)], ind, k - 1);
}

int query(trie * p, int ind, int k)
{
    if(k < 0)
        return p -> poz;
    int a = ((x[ind] >> k) & 1);
    a ^= 1;
    if(p -> F[a])
        return query(p -> F[a], ind, k - 1);
    else
        return query(p -> F[(a ^ 1)], ind, k - 1);

}

int main()
{
    f >> n;
    for(int i = 1; i <= n; i++)
    {
        int a;
        f >> a;
        x[i] = (x[i - 1] ^ a);
    }

    trie* p = rad;
    x[0] = 0;
    inserare(p, 0, 21);

    for(int i = 1; i <= n; i++)
    {
        trie* p = rad;
        int start, stop;
        stop = i;
        start = query(p, i, 21) + 1;
        if(maxi < (x[i] ^ x[start - 1]))
        {
            maxi = (x[i] ^ x[start - 1]);
            pozStart = start;
            pozStop = stop;
        }
        inserare(p, i, 21);
    }

    g << maxi << " " << pozStart << " " << pozStop;
    return 0;
}