Cod sursa(job #213597)

Utilizator madmanjonesJones the one madmanjones Data 10 octombrie 2008 16:09:37
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
# include <cstdio>

using namespace std;

# define FIN "xormax.in"
# define FOUT "xormax.out"
# define MAXN 1<<21

int N,i,Nod,max,fs,ls,a,b;
int tree[MAXN][2];
int Poz[MAXN];

    void add(int P, int ind)
    {
        int i,state,lb;
        
        state = 1; 
        for (i = 20; i >= 0; --i)
          {
              lb = 0; 
              if ((1<<i)&P) lb = 1;
              if (tree[state][lb])
                state = tree[state][lb];
              else
                state = tree[state][lb] = ++Nod;   
          }
        Poz[state] = ind;
    }
    
    void find(int P, int ind)
    {
        int i,state,lb,form;
        
        state = 1; form = 0;
        for (i = 20; i >= 0; --i)
          {
              lb = 0;
              if ((1<<i)&P) lb = 1;
              if (lb == 0)
                {
                  if (tree[state][1])
                    {
                       state = tree[state][1];
                       form |= 1<<i;
                    }
                  else
                    state = tree[state][0];
                }
              else
                {
                  if (tree[state][0])
                    {
                       state = tree[state][0];
                       form |= 1<<i;
                    }
                  else
                    state = tree[state][1];
                }
          }
        if (form > max)
          {
             max = form;
             fs = Poz[state]+1;
             ls = ind;
          }
    }

    int main()
    {
        freopen(FIN,"r",stdin);
        freopen(FOUT,"w",stdout);
        
        scanf("%d",&N);
        
        Nod = 1;
        scanf("%d",&a);
        add(a,1);
        max = a; fs = 1; ls = 1;
        
        for (i = 2; i <= N; ++i)
          {
             scanf("%d",&b);
             a ^= b;
             add(a,i);
             find(a,i);
          }
          
        printf("%d %d %d",max,fs,ls);
        
        return 0;
    }