Cod sursa(job #3146922)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 23 august 2023 10:55:55
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>
using namespace std;

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

int sor[100001];
int st = 0, dr = 1;

struct Trie{
    int lastAp;
    Trie *fiu[2];
    Trie(){
        fiu[0] = fiu[1] = NULL;
        lastAp = -1;
    }
};

Trie *root = new Trie;

void cauta(Trie *nod, int poz, int bit)
{
    if(bit == -1)
    {
        if((sor[poz] ^ sor[nod->lastAp]) > (sor[dr] ^ sor[st]))
        {
            dr = poz;
            st = nod->lastAp;
        }
        return;
    }
    int f = 1;
    if(sor[poz] & (1 << bit))
        f = 0;
    if(nod->fiu[f] == NULL)
        cauta(nod->fiu[1 ^ f], poz, bit - 1);
    else
        cauta(nod->fiu[f], poz, bit - 1);
}

void baga(Trie *nod, int poz, int bit)
{
    if(bit == -1)
    {
        nod->lastAp = poz;
        return;
    }
    int f = 0;
    if(sor[poz] & (1 << bit))
        f = 1;
    if(nod->fiu[f] == NULL)
        nod->fiu[f] = new Trie;
    baga(nod->fiu[f], poz, bit - 1);
}

int main()
{
    int n, x;
    in >> n;
    for(int i = 1; i <= n; i++)
    {
        in >> x;
        sor[i] = sor[i - 1] ^ x;
    }
    baga(root, 0, 20);
    for(int i = 1; i <= n; i++)
    {
        cauta(root, i, 20);
        baga(root, i, 20);
    }
    out << (sor[dr] ^ sor[st]) << " " << st + 1 << " " << dr;
    return 0;
}