Cod sursa(job #796957)

Utilizator mipsPavel Mircea mips Data 13 octombrie 2012 01:15:47
Problema Xor Max Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <fstream>
#include <stdlib.h>
#include <iostream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
#define LOGMAX 22

typedef struct node
{
    node* zeroNode;
    node* oneNode;
    int minim;
    int maxim;
}node;
node* alocNode()
{
    node* no = (node*)malloc(sizeof(node));
    no->minim = 100001;
    no->maxim = -1;
    no->oneNode =0;
    no->zeroNode =0;
}
void putVal(node* root,int level,int val,int poz)
{

    if (val&(1<<level))
    {
        if (!root->oneNode)
        root->oneNode = alocNode();

        if (level!=0)
            putVal(root->oneNode , level - 1,val,poz);
    }
    else
    {
        if (!root->zeroNode)
        root->zeroNode = alocNode();

        if (level!=0)
            putVal(root->zeroNode , level - 1,val,poz);
    }
    root->minim = min(root->minim,poz);
    root->maxim = max(root->maxim,poz);
}

int lastSeen[100001];

int main()
{
    int n;
    fin >> n;
    node* root = alocNode();
    int xorval=0;

    int xorValues[100001];
    for (int i=0;i<n;i++)
    {
        int a;
        fin >> a;
        xorval^=a;
        putVal(root,LOGMAX,xorval,i);
        xorValues[i] = xorval;
    }
    int finalRes=0;
    for (int i=0;i<n;i++)
    {
        node* iter = root;
        int res=0;
        for (int j=LOGMAX;j>=0;j--)
        {
            if (xorValues[i]&(1<<j))
            {
                if (iter->zeroNode)
                {
                    iter = iter->zeroNode;
                    res+=1<<j;
                }
                else
                    iter = iter->oneNode;
            }
            else
            {
                if (iter->oneNode)
                {
                    iter = iter->oneNode;
                    res+=1<<j;
                }
                else
                    iter = iter->zeroNode;
            }
        }
        finalRes = max(finalRes,res);


    }
    //cout << finalRes;


    for (int i=0;i<100001;i++)
    lastSeen[i]=-1;

    int startMin=0;
    int stopMin=100001;

    for (int i=0;i<n;i++)
    {
        if (lastSeen[xorValues[i]]!=-1)
        {
            if ((i-lastSeen[xorValues[i]])<stopMin-startMin)
            {
                stopMin = i;
                startMin = lastSeen[xorValues[i]];
            }
        }
        lastSeen[xorValues[i]^ finalRes] = i;
    }

    fout << finalRes <<" "<< startMin+2 <<" "<< stopMin+1<<endl;
}