Cod sursa(job #1964409)

Utilizator MaligMamaliga cu smantana Malig Data 13 aprilie 2017 13:42:51
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <iostream>
#include <fstream>

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

const int NMax = 1e5 + 5;
const int bitMax = 35;
typedef long long ll;

ll N;

struct nodTrie {
    ll poz;
    nodTrie *next[2];
    nodTrie() {
        poz = 0;
        next[0] = next[1] = nullptr;
    }
} root;

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

int main () {
    in>>N;

    bool bits[bitMax + 5];
    for (int k=0;k<=bitMax;++k) {
        bits[k] = 0;
    }
    update(root,bits,0,0);

    ll xorSum = 0,mx = -1,start = -1,stop = -1;
    for (ll i=1;i<=N;++i) {
        ll val;
        in>>val;
        xorSum ^= val;

        ll temp = xorSum;
        for (ll k=1;k <= bitMax;++k) {
            bits[bitMax-k] = (temp & 1);
            temp >>= 1;
        }

        /*
        for (int k=0;k<bitMax;++k) {
            cout<<bits[k];
        }
        cout<<'\n';
        //*/

        ll poz = 0, lftSum = 0;
        query(root,bits,0,poz,lftSum,0);
        //cout<<xorSum<<' '<<lftSum<<' '<<poz<<'\n';
        ll maxSum = lftSum ^ xorSum;

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

        update(root,bits,0,i);
    }

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

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

void query(nodTrie& nod,bool const * const bits,ll ind,ll& poz,ll& mx,ll mask) {
    if (ind == bitMax) {
        mx = mask;
        poz = nod.poz;
        return;
    }

    if (bits[ind] == 0) {
        nodTrie *urm;
        ll 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;
        ll 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);
    }

    /*
    if (nod.poz != 0 && mx < mask) {
        mx = mask;
        poz = nod.poz;
    }
    */
}

void update(nodTrie& nod,bool const * const bits,ll ind,ll 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);
}