Cod sursa(job #880981)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 17 februarie 2013 16:16:14
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#define nmax 100100
#define amax (1<<22)
using namespace std;

int N,A[nmax],Arb[amax];
int Answer,Start=1,End=1;

void Add(int Nod,int X,int bit) {

    if(bit<0) {
        Arb[Nod]=X;
        return;
        }

    if((A[X]&(1<<bit))==0)
        Add((Nod<<1),X,bit-1);
    else
        Add((Nod<<1)+1,X,bit-1);

    Arb[Nod]=Arb[(Nod<<1)]|Arb[(Nod<<1)+1];

}
int Query(int Nod,int X,int bit) {

    if(bit<0)
        return Arb[Nod];
    else
    if(((X&(1<<bit))&&Arb[(Nod<<1)])||!Arb[(Nod<<1)+1])
        return Query((Nod<<1),X,bit-1);
    else
        return Query((Nod<<1)+1,X,bit-1);

}
int main() {

    int i,P;
    ifstream in("xormax.in");
    ofstream out("xormax.out");

    in>>N;
    for(i=1;i<=N;i++) {

        in>>A[i];
        A[i]^=A[i-1];

        P=Query(1,A[i],20);
        Add(1,i,20);

        if(A[i]>(A[i]^A[P]))
            P=0;

        if((A[i]^A[P])>Answer) {
            Answer=A[i]^A[P];
            Start=P+1;
            End=i;
            }

        }

    out<<Answer<<' '<<Start<<' '<<End<<'\n';

    in.close();
    out.close();

    return 0;

}