Cod sursa(job #2838089)

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

using namespace std;

const int PMAX = 65536;

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

trie* root = new trie();

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

    add( root->bits[x/p], x % p, p / 2, i );
}

pair <int, int> srch( trie* root, int x, int p, int ans ) {
    if ( p == 0 ) return { ans, root->i };
    if ( root->bits[!(x/p)] == NULL ) return srch( root->bits[ (x/p)], x % p, p / 2, ans * 2 + 0 );
    if ( root->bits[!(x/p)] != NULL ) return srch( root->bits[!(x/p)], x % p, p / 2, 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, 1 );
    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;
}