Cod sursa(job #3332159)

Utilizator Grama2008Grama Andrei Teodor Grama2008 Data 4 ianuarie 2026 17:54:05
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;

const int N=1e5+5;

struct trie {
    trie* fiu[2];
    int pos;
    trie() {
        pos=-1;
        fiu[0]=fiu[1]=nullptr;
    }
};

void add(trie*&curr, int bit, int num, int pos) {
    if (curr==nullptr) {
        curr=new trie;
    }
    if (bit==-1) {
        curr->pos=max(curr->pos, pos);
        return;
    }
    if ((1<<bit)&num) {
        add(curr->fiu[1], bit-1, num, pos);
    }
    else {
        add(curr->fiu[0], bit-1, num, pos);
    }
}

pair<int,int>findbest(trie*&curr, int bit, int num) {
    if (bit==-1) {
        return {0,curr->pos};
    }
    int best=((num>>bit)&1)^1;
    if (curr->fiu[best]!=nullptr) {
        pair<int,int>y=findbest(curr->fiu[best], bit-1, num);
        return {y.first+(1<<bit),y.second};
    }
    else {
        return findbest(curr->fiu[best^1], bit-1, num);
    }
}

signed main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,mx=0,st=1,dr=1,curr=0;cin>>n;
    trie* root=nullptr;
    for (int i=1;i<=n;i++) {
        add(root, 20, curr,  i-1);
        int a;cin>>a;
        curr^=a;
        pair<int,int> x=findbest(root, 20, curr);
        if (x.first>mx) {
            mx=x.first;
            st=x.second+1;
            dr=i;
        }
    }
    cout<<mx<<' '<<st<<' '<<dr;
    return 0;
}