Cod sursa(job #976063)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 22 iulie 2013 14:46:58
Problema Xor Max Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f("xormax.in");
ofstream g("xormax.out");

#define x first
#define y second
#define mp make_pair
#define LE 100666

int nr_nodes[LE*26];
int fap[LE*26],a[LE];

void update(int j,int value) {
    int nod=1;

    for(int i=20; i>=0; --i) {
        nr_nodes[nod]++;
        if (value&(1<<i)) nod=nod*2+1;
        else nod*=2;
    }

    ++nr_nodes[nod];
    if (fap[nod]==0) fap[nod]=j;
}

pair<int,int> query(int value) {

    pair<int,int> res;
    res=mp(0,0);
    int nod=1;

    for(int i=20; i>=0; --i) {
         res.x<<=1;

        if (value&(1<<i)) {
            if (nr_nodes[nod*2]>0) nod*=2;
            else nod=nod*2+1,res.x++;
        } else {
            if (nr_nodes[nod*2+1]>0) nod=nod*2+1,res.x++;
            else nod*=2;
        }
    }
    res.y=fap[nod];

    return res;
}

int n,i;
int result;
pair<int,int> ind ;

int main() {
    f>>n;
    int xor_val=0;
    for(i=1; i<=n; ++i) f>>a[i];

    for(i=0; i<=n; ++i) {
        xor_val^=a[i];
        update(i,xor_val);

        if (i>0) {
            pair<int,int> Xo=query(xor_val);

            if ((Xo.x^xor_val)>result) {
                result=xor_val^Xo.x;
                ind=mp(Xo.y+1,i);
            }
        }
    }

    g<<result<<" "<<ind.x<<" "<<ind.y<<'\n';
  //  cout<<result<<'\n'<<ind.x<<" "<<ind.y<<'\n';



    f.close();
    g.close();
    return 0;
}