Cod sursa(job #3004047)

Utilizator octavi26octavian octavi26 Data 16 martie 2023 09:15:12
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <bits/stdc++.h>
#define N 100008

using namespace std;

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

int n;
int v[N];

struct Node
{
    int nr;
    int ap;
    int poz;
    Node *zero, *unu;
    Node(){
        nr = 0;
        ap = 0;
        zero = 0;
        unu = 0;
    }
};

Node *root = new Node;

void Add( Node *nod, int i, int x, int poz )
{
    if( i == -1 )
    {
        nod->nr = x;
        nod->poz = poz;
        return;
    }
    if( ((x & ( 1 << i )) >> i) == 0 )
    {
        if( nod->zero == 0 )
        {
            nod->ap++;
            nod->zero = new Node;
        }
        Add( nod->zero, i-1, x, poz );
    }
    else
    {
        if( nod->unu == 0 )
        {
            nod->ap++;
            nod->unu = new Node;
        }
        Add( nod->unu, i-1, x, poz );
    }
}

void Delete( Node *nod, int i, int x, bool &sters )
{
    if( i == -1 )
    {
        nod->nr = 0;
    }
    else
    {
        if( ((x & ( 1 << i )) >> i) == 0 )
        {
            Delete( nod->zero, i-1, x, sters );
            if( sters )
                nod->zero = 0, nod->ap--;
        }
        else
        {
            Delete( nod->unu, i-1, x, sters );
            if( sters )
                nod->unu = 0, nod->ap--;
        }
    }

    if( nod->nr == 0 && nod->ap == 0 && nod != root )
    {
        delete nod;
        sters = 1;
    }
    else sters = 0;
}

pair<int, int> Search( Node *nod, int i, int x ) /// caut perechea xor pt X
{
    if( i == -1 )
    {
        return {nod->nr, nod->poz};
    }
    else
    {
        if( ((x & ( 1 << i )) >> i) == 0 )
        {
            if( nod->unu )
                return Search( nod->unu, i-1, x );
            else return Search( nod->zero, i-1, x );
        }
        else
        {
            if( nod->zero )
                return Search( nod->zero, i-1, x );
            else return Search( nod->unu, i-1, x );
        }
    }
}

void Citire()
{
    int i;
    fin >> n;
    for( i=1; i<=n; i++ )
        fin >> v[i];
}

void Rezolvare()
{
    int i;
    int mx = -1, st, dr;
    Add( root, 21, 0, 0 );
    int Xor = 0;
    for( i=1; i<=n; i++ )
    {
        Xor = Xor^v[i];
        Add( root, 21, Xor, i );
        cout << Xor << " -> ";
        pair<int, int> finder = Search( root, 21, Xor );
        cout << finder.first << ": " << (Xor^finder.first) << ", " << finder.second << "\n";

        if( (Xor^finder.first) > mx )
        {
            mx = Xor^finder.first;
            st = finder.second + 1;
            dr = i;
        }
    }
    fout << mx << " " << st << " " << dr;
}

int main()
{
    Citire();
    Rezolvare();
    return 0;
}