Cod sursa(job #2207399)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 25 mai 2018 16:55:55
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 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{
    node *next[2];
    node(){
        next[0] = next[1] = NULL;
    }
};

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

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 0;
    if(nodeCurr->next[1 - *s] != NULL)
        return (1<<(21 - depth)) + 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 curr = 0;
    for(int i = 1; i <= n; ++ i){
        curr = curr ^ v[i];
        add(root, transf(curr), 0);
    }
    
    curr = 0;
    int maxim = -DIM, start = 1, finish = 1;
    for(int i = 1; i <= n; ++ i){
        curr = curr ^ v[i];
        int solCurr = search(root, transf(curr), 1);
        if(solCurr > maxim){
            maxim = solCurr;
            start = i + 1;
        }
//        else if(solCurr == maxim){
//
//        }
    }
    curr = 0;
    for(int i = start; i <= n; ++ i){
        curr = curr ^ v[i];
        if(curr == maxim){
            finish = i;
            break;
        }
    }
    out<<maxim<<" "<<start<<" "<<finish;;
//    1 0 5 4 2
//
//    100
//    000
//    101
//    001
//    010
    
    return 0;
}