Cod sursa(job #2918183)

Utilizator francescom_481francesco martinut francescom_481 Data 10 august 2022 13:39:45
Problema Xor Max Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");
#define cin fin
#define cout fout

#define N 100005
int n, st, dr, a[N];

struct Trie
{
    Trie *zero, *unu;
    int poz;
};
Trie *trie = new Trie;
void adauga(int x, int ind)
{
    Trie *p = trie;
    for(int i = 22 ; i >= 0 ; i--)
    {
        if(((x>>i)&1) == 1)
        {
            if(p->unu == NULL)
            {
                p->unu = new Trie;
                p->unu->zero = NULL;
                p->unu->unu = NULL;
            }
            p = p->unu;
        }
        else
        {
            if(p->zero == NULL)
            {
                p->zero = new Trie;
                p->zero->unu = NULL;
                p->zero->zero = NULL;
            }
            p = p->zero;
        }
    }
    p->poz = ind;
}
int fa(int a[])
{
    adauga(0,0);
    int maxim = 0;
    int xr = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        xr ^= a[i];
        Trie *p = trie;
        int x = 0;
        for(int j = 22 ; j >= 0 ; j--)
        {
            if(((xr>>j)&1) == 1)
            {
                if(p->zero == NULL)
                {
                    x |= (1<<j);
                    p = p->unu;
                }
                else p = p->zero;
            }
            else
            {
                if(p->unu == NULL)
                {
                    p = p->zero;
                }
                else
                {
                    x |= (1<<j);
                    p = p->unu;
                }
            }
        }
        if((x^xr) > maxim)
        {
            maxim = x^xr;
            dr = i;
            st = p->poz;
        }
        adauga(xr,i);
    }
    return maxim;
}

int main() {

    trie->unu = NULL;
    trie->zero = NULL;
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i];
    }
    cout << fa(a) << " " << st+1 << " " << dr;
    return 0;
}