Cod sursa(job #2212386)

Utilizator NOSCOPEPROKENDYMACHEAMACUMVREAU NOSCOPEPROKENDY Data 13 iunie 2018 22:03:40
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <fstream>
#define DIM 100002

using namespace std;

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

int n, v[DIM], aux[50];

struct node{
    int poz;
    node *next[2];
    node(){
        next[0] = next[1] = NULL;
        poz = 0;
    }
};

void add(node *nodeCurr, int *s, int depth, int poz){
    if(depth == 22){
        nodeCurr->poz = poz;
        return;
    }
    if(nodeCurr->next[*s] == NULL)
        nodeCurr->next[*s] = new node;
    add(nodeCurr->next[*s], s + 1, depth + 1, poz);
}

int* transf(int x){
    int vect[50];
    int k = 0;
    while(x != 0){
        vect[++k] = x % 2;
        x /= 2;
    }
    for(int i = 1; i <= 21; ++ i){
        aux[i] = 0;
    }
    for(int i = k; i >= 1; -- i)
        aux[21 - k + i] = vect[k - i + 1];


    return aux + 1;
}

int search(node *nodeCurr, int *s, int depth){
    if(depth == 22)
        return nodeCurr->poz;
    if(nodeCurr->next[0] == nodeCurr->next[1])
        return 0;
    if(nodeCurr->next[1 - *s] != NULL)
        return search(nodeCurr->next[1 - *s], s + 1, depth + 1);
    else
        return search(nodeCurr->next[*s], s + 1, depth + 1);
}

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

    in>>n;
    for(int i = 1; i <= n; ++ i)
        in>>v[i];
    node *root = new node;
    int maxim = -DIM, start, stop;
    add(root, transf(0), 0, 0);
    for(int i = 1; i <= n; ++ i){
        v[i] = v[i] ^ v[i - 1];
        int poz = search(root, transf(v[i]), 0);
        if((v[i] ^ v[poz]) > maxim){
            maxim = v[i] ^ v[poz];
            start = poz + 1;
            stop = i;
        }
        add(root, transf(v[i]), 0, i);
    }

    out<<maxim<<" "<<start<<" "<<stop;
    //    1 0 5 4 2
    //
    //    100
    //    000
    //    101
    //    001
    //    010

    return 0;
}