Cod sursa(job #3354276)

Utilizator dobreraduDobre Radu Fabian dobreradu Data 17 mai 2026 11:53:45
Problema Xor Max Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int NMAX = 1e5 + 5;
int spx[NMAX];
struct Trie{
    int idx;
    Trie* bits[2];
    Trie(){
        idx = 0;
        bits[0] = bits[1] = nullptr;
    }
};

void insert( Trie* root, int x, int idx ){
    Trie *curr = root;
    for( int i = 20; i >= 0; i-- ){
        int bit = ( x >> i) & 1 ;
        if( curr->bits[bit] == nullptr )
            curr -> bits[bit] = new Trie();
        curr = curr->bits[bit];
    }
    curr->idx = idx;
}
int query( Trie* root, int x) {
    Trie *curr = root;
    for( int i = 20; i>= 0; i-- ){
        int bit = ( x >> i) & 1 ;
        if( curr->bits[!bit] != nullptr )
            curr = curr->bits[!bit];
        else{
            if( curr->bits[bit] != nullptr )
                curr = curr->bits[bit];
            else 
                return curr->idx;
        }
    }
    return curr->idx;
}

int main(){
    int n, x;
    fin >> n;
    Trie* root = new Trie();
    insert(root, 0, 0);
    int maxXor = 0, l, r;

    for( int i = 1; i <= n; i++ ){
        fin >> x;
        spx[i] ^= spx[x-1] ^ x;
        int k = query(root, spx[i]);
        if( maxXor < (spx[k] ^ spx[i]) ){
            maxXor = spx[k] ^ spx[i];
            l = k+1;
            r = i;
        }
        insert(root, spx[i], i);

    }
    
    fout << maxXor << ' ' <<  l << " " << r << "\n";
    return 0;
}