Cod sursa(job #1740702)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 12 august 2016 02:14:35
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <bits/stdc++.h>
using namespace std;

ifstream in ( "xormax.in"  );
ofstream out( "xormax.out" );

int N, X, XOR, MAX, val, pos, st, dr;

struct T {

    int cntC, cntN, pos;
    T *ch[2];

    T() {
        this -> cntC = this -> cntN = 0; this -> pos = -1;
        this -> ch[0] = this -> ch[1] = NULL;
    }
} *root = new T;

void insert( T *&t, int X, int p, int pos ) {

    if( p < 0 ) {
        t -> cntC ++; t -> pos = pos;
        return;
    }

    int Z = ((X & (1 << p)) > 0) ? 1 : 0;

    if( t -> ch[Z] == NULL ) {
        t -> ch[Z] = new T;
        t -> cntN ++;
    }

    insert( t -> ch[Z], X, p - 1, pos );
    return;
}

void query( T *&t, int &val, int &pos, int X, int Y, int p ) {

    if( p < 0 ) {
        val = Y; pos = t -> pos;
        return;
    }

    int Z = ((X & (1 << p)) > 0) ? 1 : 0;

    if( t -> ch[1 - Z] != NULL ) {
        query( t -> ch[1 - Z], val, pos, X, Y + (1 << p) * 1, p - 1 );
        return;
    }

    if( t -> ch[Z - 0] != NULL ) {
        query( t -> ch[Z - 0], val, pos, X, Y + (1 << p) * 0, p - 1 );
        return;
    }

    return;
}

int main( int argc, const char *argv[] ) {

    in >> N; MAX = -1;
    insert( root, XOR, 30, 0 );

    for( int i = 1; i <= N; i ++ ) {
        in >> X; XOR ^= X; val = -1;

        query( root, val, pos, XOR, 0, 30 );
        insert( root, XOR, 30, i );

        if( MAX < val ) {
            MAX = val;
            st = pos + 1;
            dr = i;
        }
    }

    out << MAX << " " << st << " " << dr << "\n";

    return 0;
}