Cod sursa(job #1801487)

Utilizator HuskyezTarnu Cristian Huskyez Data 9 noiembrie 2016 08:05:05
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <iostream>
#include <fstream>

#define infile "xormax.in"
#define outfile "xormax.out"

using namespace std;

ifstream in(infile);
ofstream out(outfile);

struct trieNode{
    trieNode* left;
    trieNode* right;
    int poz;

    trieNode()
    {
        left = NULL;
        right = NULL;
        poz = 0;
    }
};

int n, x;
int v[100005];

int nrMaxBiti, maxi;

trieNode* root = new trieNode;

int rightPos, leftPos, max_xor = -1;



void inserare(trieNode* node, int bit, int val, int ind)
{
    if(bit == -1){
        node->poz = ind;
        return;
    }
    if((val>>bit) & 1){
        if(node->right == NULL){
            trieNode* n = new trieNode;
            node->right = n;
        }
        inserare(node->right, bit-1, val, ind);
    }else{
        if(node->left == NULL){
            trieNode* n = new trieNode;
            node->left = n;
        }
        inserare(node->left, bit-1, val, ind);
    }

}

int search(trieNode* node, int bit, int val)
{
    if(bit == -1){
        return node->poz;
    }else{
        bool bitValue = ((val >> bit) & 1);

        if(bitValue == true){
            if(node->left != NULL){
                search(node->left, bit-1, val);
            }else{
                search(node->right, bit-1, val);
            }
        }else{
            if(node->right != NULL){
                search(node->right, bit-1, val);
            }else{
                search(node->left, bit-1, val);
            }
        }
    }
}

int main()
{
    in >> n;

    for(int i=1; i<=n; i++){
        in >> x;
        v[i] = v[i-1] ^ x;
        maxi = max(maxi, x);
    }

    for(;maxi; maxi/=2){
        nrMaxBiti++;
    }

    inserare(root, nrMaxBiti, 0, 0);

    for(int i=1; i<=n; i++){
        int ind = search(root, nrMaxBiti, v[i]);

        if((v[i]^v[ind]) > max_xor){
            max_xor = (v[i]^v[ind]);
            leftPos = ind + 1;
            rightPos = i;
        }
        inserare(root, nrMaxBiti, v[i], i);
    }

    out << max_xor << ' ' << leftPos << ' ' << rightPos << '\n';

    return 0;
}