Cod sursa(job #1700668)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 10 mai 2016 22:55:23
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
///Cu trie
#include <cstdio>
using namespace std;

const int MB  = 1<<21;
const int INF = 1e9;

int a, b, smax;

struct NOD {
    int poz;
    NOD  *barn[2];
    bool cbarn[2];

    NOD(void){
        cbarn[0] = false;
        cbarn[1] = false;
    }
};
NOD *root;

inline void insert(int arg, int poz) {
    NOD *c = root;
    for(int m=MB; m; m>>=1) {
        if(arg&m) {
            if(!c->cbarn[1]) {
                c->cbarn[1] = 1;
                c-> barn[1] = new NOD();
                c-> poz     = poz;
            }
            c = c->barn[1];
        }
        else {
            if(!c->cbarn[0]) {
                c->cbarn[0] = 1;
                c-> barn[0] = new NOD();
                c-> poz     = poz;
            }
            c = c->barn[0];
        }
    }
    c->poz = poz;
}

inline void query(int arg, int poz) {
    NOD *c  = root;
    int ans = 0;

    for(int m=MB; m; m>>=1) {
        if(arg&m) {
            if(c->cbarn[0]) {
                ans|= m;
                c   = c->barn[0];
            }
            else {
                c   = c->barn[1];
            }
        }
        else {
            if(c->cbarn[1]) {
                ans|= m;
                c   = c->barn[1];
            }
            else {
                c   = c->barn[0];
            }
        }
    }

    if(ans>smax) {
        smax = ans;
        a    = c->poz + 1;
        b    = poz;
    }
}

int main(void) {
    FILE *fi = fopen("xormax.in","r");
    FILE *fo = fopen("xormax.out","w");
    int n, t, s;

    root = new NOD();
    smax = -1;
    s    = 0;
    insert(0, 0);

    fscanf(fi,"%d",&n);
    for(int i=1; i<=n; ++i) {
        fscanf(fi,"%d",&t);
        s^=t;
        query (s, i);
        insert(s, i);
    }

    fprintf(fo,"%d %d %d\n",smax,a,b);

    fclose(fi);
    fclose(fo);
    return 0;
}