Cod sursa(job #3352514)

Utilizator Andreea3425Diaconu Andreea Andreea3425 Data 28 aprilie 2026 12:11:38
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <bits/stdc++.h>

using namespace std;

#define N 100000
#define X 1<<30

pair <int, int> mx;
int v[N+2];

struct Nod{
    int k;
    Nod *next[2];

    Nod():k(0){
        next[0]=next[1]=0;
    }
};

struct Trie{
    Nod *nod;

    void up(int xx, int poz){
        int i,a;
        Nod *node=nod;

        for (i=31; i>=0; i--){
            a=!!(xx&(1<<i));

            if ((node->next[a])==0)
                node->next[a]=new Nod();

            node=(node->next[a]);
            (node->k)=poz;
        }
        return;
    }

    pair <int, int> ins(int xx){
        int i,a;
        Nod *node=nod;
        pair <int, int> q=make_pair(0, X);

        for (i=31; i>=0; i--){
            a=!!(xx&(1<<i));

            if ((node->next[a^1])!=0){
                node=(node->next[a^1]);
                q.first|=(1<<i);
                q.second=min(q.second, (node->k));
            }else if ((node->next[a])!=0){
                node=(node->next[a]);
                q.second=min(q.second, (node->k));
            }
        }

        return q;
    }
}trie;

int main()
{
    ifstream cin ("xormax.in");
    ofstream cout ("xormax.out");

    int n,i,x;

    cin >> n;

    trie.nod=new Nod();
    for (i=1; i<=n; i++){
        cin >> v[i];
        v[i]^=v[i-1];
    }

    trie.up(0, 0);
    x=-X;
    for (i=0; i<n; i++){
        pair <int, int> q=trie.ins(v[i]);
        trie.up(v[i], i);

        if (x<q.first){
            x=q.first;
            mx=make_pair(q.second, i);
        }
    }

    cout << x << ' '  << mx.first+1 << ' ' << mx.second << '\n';

    return 0;
}