Cod sursa(job #3135100)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 1 iunie 2023 20:24:54
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <bits/stdc++.h>
using namespace std;

int sor[100001];
map <int, int> mp[21];

struct Trie{
    int last, nivel;
    Trie *zero, *unu;
    Trie(int ult){
        zero = unu = NULL;
        last = ult;
        nivel = 21;
    }
};

Trie *root = new Trie(-1);

void baga(Trie *nod, int poz)
{
    nod->last = poz;
    if(nod->nivel == 0)
        return;
    if((1 << (nod->nivel - 1)) & sor[poz])
    {
        if(nod->unu == NULL)
        {
            nod->unu = new Trie(poz);
            nod->unu->nivel = nod->nivel - 1;
        }
        baga(nod->unu, poz);
    }
    else
    {
        if(nod->zero == NULL)
        {
            nod->zero = new Trie(poz);
            nod->zero->nivel = nod->nivel - 1;
        }
        baga(nod->zero, poz);
    }
}

int p;

int cauta(Trie *nod, int poz)
{
    if(nod->nivel == 0)
    {
        p = nod->last;
        return 0;
    }
    if((1 << (nod->nivel - 1)) & sor[poz])
    {
        if(nod->zero != NULL)
            return (1 << (nod->nivel - 1)) + cauta(nod->zero, poz);
        else
            return cauta(nod->unu, poz);
    }
    else
    {
        if(nod->unu != NULL)
            return (1 << (nod->nivel - 1)) + cauta(nod->unu, poz);
        else
            return cauta(nod->zero, poz);
    }
}

int main() {
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, x;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> x;
        sor[i] = sor[i - 1] ^ x;
    }
    root->last = 3;
    baga(root, 0);
    int max1 = 0, st, dr;
    for(int i = 1; i <= n; i++)
    {
        x = cauta(root, i);
        if(x > max1)
        {
            max1 = x;
            st = p + 1;
            dr = i;
        }
        baga(root, i);
    }
    cout << max1 << " " << st << " " << dr;
    return 0;
}