Cod sursa(job #1964469)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 13 aprilie 2017 14:08:41
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.47 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");

const int bitMax = 22;

int N;

struct nodTrie {
    int poz;
    nodTrie *next[2];
    nodTrie() {
        poz = 0;
        next[0] = next[1] = nullptr;
    }
} root;
// root - radacina trie-ului
// nod.poz = cel mai mare indice i astfel incat v[1]^v[2]^...^v[i] = suma xor
//                                ce se obtine pe traseul de la root la nod
// next[0] = pointer catre un nod din trie, daca s-ar urma o muchie 0
// next[1] = pointer catre un nod din trie, daca s-ar urma o muchie 1

void query(nodTrie&,bool const * const,int,int&,int&,int);
void update(nodTrie&,bool const * const,int,int);

int main () {
    in>>N;

    // bits[i] = al (i+1)-lea cel mai semnificativ bit din reprezentarea binara a unei sume xor
    bool bits[bitMax + 5];
    for (int k=0;k<=bitMax;++k) {
        bits[k] = 0;
    }

    // se introduce in trie o suma xor = 0
    update(root,bits,0,0);

    // xorSum = suma xor a primelor i elemente din input
    int xorSum = 0,mx = -1,start = -1,stop = -1;
    for (int i=1;i<=N;++i) {
        int val;
        in>>val;
        xorSum ^= val;

        // se completeaza vectorul bits cu bit-i din reprezentarea binara a lui xorSum
        int temp = xorSum;
        for (int k=1;k <= bitMax;++k) {
            bits[bitMax-k] = (temp & 1);
            temp >>= 1;
        }

        int poz = 0, lftSum = 0;
        query(root,bits,0,poz,lftSum,0);
        // lftSum = o suma xor intre doua indice [1,poz], astfel incat lftSum ^ xorSum sa fie maxim
        // poz = cel mai mare indice care da un astfel de lftSum
        int maxSum = lftSum ^ xorSum;

        if (mx < maxSum) {
            mx = maxSum;
            start = poz+1;
            stop = i;
        }

        update(root,bits,0,i);
        // se intoduce noul xorSum in trie
    }

    out<<mx<<' '<<start<<' '<<stop<<'\n';

    in.close();out.close();
    return 0;
}


// cauta o suma xor mx, astfel incat xorSum ^ mx sa fie maxim
// mask = numarul care se obtine parcurgand drumul de la root la nod
// mx ^ xorSum va fi intotdeauna mai mare sau egal cu xorSum, deoarece s-a introdus
// o suma xor = 0 in trie
void query(nodTrie& nod,bool const * const bits,int ind,int& poz,int& mx,int mask) {
    if (ind == bitMax) {
        mx = mask;
        poz = nod.poz;
        return;
    }

    if (bits[ind] == 0) {
        nodTrie *urm;
        int bt;
        if (nod.next[1] != nullptr) {
            urm = nod.next[1];
            bt = 1;
        }
        else {
            urm = nod.next[0];
            bt = 0;
        }

        query(*urm,bits,ind+1,poz,mx,mask*2 + bt);
    }
    else {
        nodTrie *urm;
        int bt;
        if (nod.next[0] != nullptr) {
            urm = nod.next[0];
            bt = 0;
        }
        else {
            urm = nod.next[1];
            bt = 1;
        }

        query(*urm,bits,ind+1,poz,mx,mask*2 + bt);
    }
}


// introduce o suma xor in trie.
// fiecare xorSum = v[1]^v[2]^...^v[i] se va introduce dupa ce se gaseste
// un raspuns pentru pozitia i
void update(nodTrie& nod,bool const * const bits,int ind,int i) {
    if (bitMax == ind) {
        nod.poz = i;
        return;
    }

    nodTrie *urm = nod.next[bits[ind]];
    if (urm == nullptr) {
        urm = new nodTrie;
        nod.next[bits[ind]] = urm;
    }
    update(*urm,bits,ind+1,i);
}