Cod sursa(job #1798807)

Utilizator martonsSoos Marton martons Data 5 noiembrie 2016 14:16:59
Problema Xor Max Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>

#define INF (1<<21)
using namespace std;

struct trie{
    trie *b[2];
    int pos;
};

trie *t;
int v[100005], sum[100005];

void t_add(int val, int pos){
    trie *crt = t;

    for(int bitnum = 20;bitnum>=0;bitnum--){
        if(crt->b[(val>>bitnum) & 1]==NULL){
            crt->b[(val>>bitnum) & 1] = new trie;
            crt->b[(val>>bitnum) & 1]->b[0] = NULL;
            crt->b[(val>>bitnum) & 1]->b[1] = NULL;
        }
        crt = crt->b[(val>>bitnum) & 1];
    }

    crt->pos = pos;
}

int t_query(int val){
    trie *crt = t;

    for(int bitnum = 20;bitnum>=0;bitnum--){
        if(crt->b[!((val>>bitnum) & 1)]!=NULL)crt = crt->b[!((val>>bitnum) & 1)];
        else crt = crt->b[(val>>bitnum) & 1];
    }

    return crt->pos;
}

int main()
{
    t = new trie;
    t->b[0] = NULL;
    t->b[1] = NULL;
    ifstream in("xormax.in");

    int n;
    in>>n;

    int crtsum=0;
    int best=-INF;
    int b_start=-1;
    int b_end=-1;

    t_add(0, 0);

    for(int i = 1;i<=n;i++){
        in>>v[i];
        crtsum ^= v[i];
        sum[i] = crtsum;
        t_add(crtsum, i);

        int cbest = t_query(crtsum);

        if((crtsum^sum[cbest])>best){
            best = crtsum^sum[cbest];
            b_start = cbest+1;
            b_end = i;
        }
        else if((crtsum^sum[cbest]) == best){
            if(b_end - b_start > i - cbest){
                b_end = i;
                b_start = cbest+1;
            }
        }
    }

    ofstream out("xormax.out");

    out<<best<<" "<<b_start<<" "<<b_end;
    return 0;
}