Cod sursa(job #2990793)

Utilizator raulandreipopRaul-Andrei Pop raulandreipop Data 8 martie 2023 16:05:34
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <iostream>

using namespace std;
const int nmax = 1e5 + 2;

struct node {
    node* child[2];
    int fin;
};

node* getnode ()
{
    node *ret = new node;
    ret->child[0] = 0;
    ret->child[1] = 0;
    ret->fin = 0;
    
    return ret;
}

void addNum (node* root , int x, int b , int index)
{
    bool bit = ((x & (1 << b)) > 0) ? 1 : 0;

    if (root->child[bit] == 0)
    {
        root->child[bit] = getnode();
    }
    if (b == 0) root->child[bit]->fin = index;
    else {
        addNum(root->child[bit] , x , b-1 , index);
    }
}

pair<int , int> query (node* nod , int x , int b , int mask)
{
    bool bit = ((x & (1 << b)) > 0) ? 1 : 0;
    pair<int , int> rez;
    if (b == -1) {
        return {mask , nod->fin};
    }
    else if (nod->child[bit^1] != 0)
    {
        return query(nod->child[bit^1] , x , b-1 , (mask | (1 << b)));
    }
    else {
        return query(nod->child[bit] , x , b-1 , (mask | (1 << b)) - (1 << b));
    }
    

}

int xp[nmax];
int a[nmax];

int main ()
{
 //   freopen("xormax.in" , "r" , stdin);
   // freopen("xormax.out" , "w" , stdout);

    int n; cin >> n;
    
    node* root = getnode();

    addNum(root , xp[0] , 20 , 0);
    int maxXor = -1;
    int st = -1 , dr = -1;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        
        xp[i] = (xp[i-1] ^ a[i]);

        pair<int , int> crt = query(root , xp[i] , 20 , 0);
        if (crt.first > maxXor)
        {
            st = crt.second;
            dr = i;
            maxXor = crt.first;
        }
        
        addNum(root , xp[i] , 20 , i);
    }


    cout << maxXor << ' ' << st + 1 << ' ' << dr << '\n';
}