Cod sursa(job #2224633)

Utilizator HaesteinnSabau Florin Vlad Haesteinn Data 24 iulie 2018 18:09:42
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

int xormax=0,xorstart=0,xorend=0,nrBits=0;
int bits[100];
int n,a[100002];

void countBits(int xmax)
{
    while(xmax>0)
    {
        xmax/=2;
        nrBits++;
    }
}

struct node
{
    int ending;
    node* edge[2]={};
}* root=new node;

void toBinary(int x)
{
    for(int i=0;i<nrBits;i++)
    {
        bits[i]=x%2;
        x/=2;
    }
}

void addTrie(int j)
{
    node* crawl=root;
    for(int i=nrBits-1;i>=0;i--)
    {
       // cout<<crawl->edge[bits[i]]<<" ";
        if(crawl->edge[bits[i]]==NULL)
        {

            node* element=new node;
            crawl->edge[bits[i]]=element;
        }

        crawl=crawl->edge[bits[i]];
    }
    crawl->ending=j;
}

void findMax(int j)
{
    node* crawl=root;
    for(int i=nrBits-1;i>=0;i--)
    {
        if(bits[i]==0&&crawl->edge[1]!=NULL)
            crawl=crawl->edge[1];
        else if(bits[i]==1&&crawl->edge[0]!=NULL)
            crawl=crawl->edge[0];
        else crawl=crawl->edge[bits[i]];
    }
    if(a[crawl->ending]^a[j]>xormax)
    {
        xormax=a[crawl->ending]^a[j];
        xorstart=crawl->ending+2;
        xorend=j+1;
    }
}


int main()
{
    int xsum=0,xmax=0;
    fin>>n;
    for(int i=0;i<n;i++)
    {
        int tmp;
        fin>>tmp;
        xsum^=tmp;
        xmax=max(xsum,xmax);
        a[i]=xsum;

    }

    countBits(xmax);
    toBinary(a[0]);
   // for(int i=nrBits-1;i>=0;i--)
  //      cout<<bits[i]<<" ";
    addTrie(0);
    if(a[0]>xormax)
    {
        xormax=a[0];
        xorstart=1;
        xorend=1;
    }
    for(int i=1;i<n;i++)
    {

        toBinary(a[i]);
        findMax(i);
        addTrie(i);
    }
    fout<<xormax<<" "<<xorstart<<" "<<xorend;
    return 0;
}