Cod sursa(job #2332251)

Utilizator borscalinCalin-Stefan Georgescu borscalin Data 30 ianuarie 2019 15:57:11
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream>
#include <fstream>

#define NMAX 100000

using namespace std;

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

class Node {
public :
    int last;
    Node* next[2];

    Node() {
        last = 0;
        next[0] = next[1] = 0;
    }
};

int n, v[1 + NMAX];
int ans, st, dr;
Node* trie = new Node;

void Insert ( int val, int poz ) {
    Node* node = trie;

    for ( int i = 20; i >= 0; --i ) {
        int bit = ( ( val & ( 1 << i ) ) > 0 ) ? 1 : 0;
        if ( ! ( node -> next[bit] ) )
            node -> next[bit] = new Node;
        node = node -> next[bit];
    }

    node -> last = poz;
}

int Search ( int val ) {
    Node* node = trie;

    for ( int i = 20; i >= 0; --i ) {
        int bit = ( ( val & ( 1 << i ) ) > 0 ) ? 1 : 0;
        if ( node -> next[!bit] )
            node = node -> next[!bit];
        else
            node = node -> next[bit];
    }

    return node -> last;
}


int main() {
    fin >> n;

    for ( int i = 1; i <= n; ++i ) {
        fin >> v[i];
        v[i] ^= v[i - 1];
    }

    ans = v[1];
    st = dr = 1;
    Insert ( v[1], 1 );
    for ( int i = 2; i <= n; ++i ) {
        int p = Search ( v[i] );
        if ( ( v[p] ^ v[i] ) > ans ) {
            ans = ( v[p] ^ v[i] );
            st = p + 1;
            dr = i;
        }
        Insert ( v[i], i );
    }

    fout << ans << ' ' << st << ' ' << dr << '\n';

    return 0;
}