Cod sursa(job #986579)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 19 august 2013 08:18:39
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 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*46];
int fap[LE*46],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];
     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);
            }
        }
    }
    if (result==0) g<<0<<" "<<1<<" "<<1<<'\n';
     g<<result<<" "<<ind.x<<" "<<ind.y<<'\n';

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