Cod sursa(job #1814168)

Utilizator grimmerFlorescu Luca grimmer Data 23 noiembrie 2016 18:22:31
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#include <cstring>
using namespace std;

const int NMaX = 100005, StartBitPow = 20, INF = 0x3f3f3f3f;

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

int v[NMaX];
int n, st, ed, max_xor = -INF;

struct Trie{
    int pos;
    Trie *children[2];

    Trie() {
        memset( children, 0, sizeof( children ) );
    }

};

Trie *T = new Trie;

int Query(Trie *node, int val, int pow){
    if(pow < 0){
        return node->pos;
    }

    int best_dir = (val & (1 << pow)) == 0;

    if(node->children[best_dir] == nullptr){
        //node->children[!best_dir] = new Trie;
        return Query(node->children[!best_dir], val, pow - 1);
    }

    return Query(node->children[best_dir], val, pow - 1);
}

void Add(Trie *node, int val, int ind, int pow){
    if(pow < 0){
        node->pos = ind;
        return;
    }

    int dir = (val & (1 << pow)) == 0;

    if(node->children[!dir] == nullptr){
        node->children[!dir] = new Trie;
    }

    Add(node->children[!dir], val, ind, pow - 1);
}

int main() {

    int i, best_pos, best_val;

    fin>>n;

    Add(T, 0, 0, StartBitPow);

    for(i = 1; i <= n; ++i){

        fin>>v[i];
        v[i] ^= v[i - 1];

        best_pos = Query(T, v[i], StartBitPow);
        best_val = v[best_pos];

        if((best_val ^ v[i]) > max_xor){

            max_xor = best_val ^ v[i];
            st = best_pos + 1;
            ed = i;

        }

        Add(T, v[i], i, StartBitPow);

    }

    fout<< max_xor << " " << st << " " << ed;

    return 0;
}