Cod sursa(job #3146924)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 23 august 2023 11:00:20
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;
    int fiu[2];
    Trie(){
        fiu[0] = fiu[1] = -1;
        lastAp = -1;
    }
}vec[2000001];
int cnt;

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

void baga(int nod, int poz, int bit)
{
    if(bit == -1)
    {
        vec[nod].lastAp = poz;
        return;
    }
    int f = 0;
    if(sor[poz] & (1 << bit))
        f = 1;
    if(vec[nod].fiu[f] == -1)
        vec[nod].fiu[f] = ++cnt;
    baga(vec[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(0, 0, 20);
    for(int i = 1; i <= n; i++)
    {
        cauta(0, i, 20);
        baga(0, i, 20);
    }
    out << (sor[dr] ^ sor[st]) << " " << st + 1 << " " << dr;
    return 0;
}