Cod sursa(job #3309813)

Utilizator AndreiNicolaescuEric Paturan AndreiNicolaescu Data 9 septembrie 2025 11:11:01
Problema Xor Max Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <bits/stdc++.h>
#define cin ci
#define cout co
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");

const int Nmax = 1e5 + 1;
const int L = 31;
int n, x, v[Nmax];

struct Node
{
    int fin = -1;
    vector<Node*> sons;
    Node(): sons(2){}
    ~Node()
    {
        for(int i = 0; i < 2; i++)
            if(this->sons[i] != nullptr)
                delete this->sons[i];
    }
};
Node* trie = nullptr;

Node* add(Node* p, int x, int bit, int idx)
{
    if(p == nullptr)
        p = new Node;
    if(bit < 0)
        p->fin = idx;
    else
    {
        int b = (x >> bit) & 1;
        p->sons[b] = add(p->sons[b], x, bit - 1, idx);
    }
    return p;
}

int query(Node* p, int x, int bit)
{
    if(p == nullptr) return -1;
    if(bit < 0) return p->fin;

    int b = (x >> bit) & 1;
    int prefer = 1 - b;
    if(p->sons[prefer] != nullptr)
        return query(p->sons[prefer], x, bit - 1);
    else
        return query(p->sons[b], x, bit - 1);
}

int main()
{
    cin >> n;
    v[0] = 0;
    int maxi = 0;
    int start = 0, finish = 0;

    trie = add(trie, 0, L - 1, 0);

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

        int j = query(trie, v[i], L - 1);
        if(j != -1 && (v[i] ^ v[j]) > maxi)
        {
            maxi = v[i] ^ v[j];
            finish = i;
            start = j + 1;
        }
        trie = add(trie, v[i], L - 1, i);
    }

    cout << maxi << " " << start << " " << finish;
    return 0;
}