Cod sursa(job #3352510)

Utilizator andreidumitrache1709andreidumitrache andreidumitrache1709 Data 28 aprilie 2026 12:03:52
Problema Xor Max Scor 65
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5;
const int SIGMA = 25;

int sp[MAXN + 1];
struct Trie {
    struct Node {
        int nxt[2] , idx;
    } t[MAXN * SIGMA + 1];
    int len = 1;
    void add( string s , int idx ) {
        int u = 1 , c;
        for( auto ch : s ) {
            c = ch - '0';
            //cout << u << ' ' << ch << '\n';
            if( !t[u].nxt[c] )
                t[u].nxt[c] = ++len;
            u = t[u].nxt[c];
        }
        if( !t[u].idx )
            t[u].idx = idx;
    }
    pair< int , int >findbest( string s ) {
        int ans = 0 , u = 1 , c , i = 20;
        for( auto ch : s ) {
            c = ch - '0';
            if( t[u].nxt[1 - c] ) {
                ans += ( 1 << i );
                u = t[u].nxt[1 - c];
            } else
                u = t[u].nxt[c];
            i--;
        }
        return { ans , t[u].idx };
    }
} trie;
int main() {
    ifstream cin( "xormax.in" );
    ofstream cout( "xormax.out" );
    int n , i , xorr , x , j , ans , l , r;
    string s;
    cin >> n;
    xorr = ans = 0;
    for( i = 1 ; i <= n ; i++ ) {
        cin >> x;
        // xor de la i la j este xor[i] ^ xor[j - 1]
        s = "";
        for( j = 20 ; j >= 0 ; j-- )
            if( xorr & ( 1 << j ) )
                s += "1";
            else
                s += "0";
        trie.add( s , i );
        xorr ^= x;
        s = "";
        for( j = 20 ; j >= 0 ; j-- )
            if( xorr & ( 1 << j ) )
                s += "1";
            else
                s += "0";
        //cout << xorr << ' ' << s << '\n';
        //cout << trie.findbest( s ).first << '\n';
        if( ans < trie.findbest( s ).first ) {
            ans = trie.findbest( s ).first;
            l = trie.findbest( s ).second;
            r = i;
        }
    }
    cout << ans << ' ' << l << ' ' << r << '\n';
    //cout << ans << '\n';
    return 0;
}