Cod sursa(job #2838091)

Utilizator Tudor06MusatTudor Tudor06 Data 23 ianuarie 2022 04:52:54
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;

const int PMAX = 20;

struct trie {
    int i;
    trie* bits[2];
};

trie* root = new trie();

void add( trie* root, int x, int p, int i ) {
    if ( p == -1 ) {
        root->i = i;
        return;
    }
    if ( !(root->bits[(int)(x>>p)] != NULL) )
        root->bits[(int)(x>>p)] = new trie();

    add( root->bits[(int)(x>>p)], x & ( ( 1 << p ) - 1 ), p - 1, i );
}

pair <int, int> srch( trie* root, int x, int p, int ans ) {
    if ( p == -1 ) return { ans, root->i };
    if ( root->bits[1 - (x>>p)] == NULL ) return srch( root->bits[  (int)(x>>p)], x & ( ( 1 << p ) - 1 ), p - 1, ans * 2 + 0 );
    if ( root->bits[1 - (x>>p)] != NULL ) return srch( root->bits[1-(int)(x>>p)], x & ( ( 1 << p ) - 1 ), p - 1, ans * 2 + 1 );
}
int main() {
    ifstream fin( "xormax.in" );
    ofstream fout( "xormax.out" );
    int n, x = 0, i, a, l, r, maxim = 0;
    fin >> n;
    add( root, 0, PMAX, 0 );
    for ( i = 1; i <= n; i ++ ) {
        fin >> a;
        x ^= a;
        pair <int, int> aux = srch( root, x, PMAX, 0 );
        if ( aux.first > maxim ) {
            l = aux.second;
            r = i;
            maxim = aux.first;
        }
        add( root, x, PMAX, i );
    }
    fout << maxim << ' ' << l + 1 << ' ' << r;
	return 0;
}