Cod sursa(job #1963939)

Utilizator MaligMamaliga cu smantana Malig Data 12 aprilie 2017 22:15:30
Problema Xor Max Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <iostream>
#include <fstream>

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

const int NMax = 1e5 + 5;
const int bitMax = 3;

int N;

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

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

int main () {
    in>>N;

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

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

        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);
        //cout<<xorSum<<' '<<lftSum<<' '<<poz<<'\n';
        int maxSum = lftSum ^ xorSum;

        if (mx < maxSum) {
            mx = maxSum;
            start = poz+1;
            stop = i;
        }
        else if (mx == maxSum && stop-start > i-(poz+1)) {
            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 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);
    }

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

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