Cod sursa(job #796964)

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

typedef struct node
{
    node* zeroNode;
    node* oneNode;
    int lastpoz;
}node;
node* alocNode()
{
    node* no = (node*)malloc(sizeof(node));
    no->lastpoz = 100001;
    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();
        root->oneNode->lastpoz = poz;
        if (level!=0)
            putVal(root->oneNode , level - 1,val,poz);
    }
    else
    {
        if (!root->zeroNode)
        root->zeroNode = alocNode();
        root->zeroNode->lastpoz = poz;
        if (level!=0)
            putVal(root->zeroNode , level - 1,val,poz);
    }
    root->lastpoz = poz;
}

int lastSeen[3000001];

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;
    int startMin=1;
    int stopMin=1;
    for (int i=0;i<n;i++)
    {
        int a;
        fin >> a;
        xorval^=a;
        putVal(root,LOGMAX,xorval,i);
        xorValues[i] = xorval;

        node* iter = root;
        int res=0;
        int pos=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;
            }
        }
        pos = iter->lastpoz;
        if (finalRes< res)
        {
            finalRes = res;
            startMin = pos+2;
            stopMin = i+1;
        }
        if (finalRes< xorValues[i])
        {
            finalRes=xorValues[i];
            startMin = 1;
            stopMin = i+1;
        }
    }
    fout << finalRes <<" "<< startMin <<" "<< stopMin<<endl;
}