Cod sursa(job #212251)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 4 octombrie 2008 21:24:56
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
# include <cstdio>

using namespace std;

# define FIN "xormax.in"
# define FOUT "xormax.out"
# define MAXN 100005

int N,i,Nod,max,fs,ls;
int A[MAXN];
int tree[1<<21][2];
int Poz[1<<21];

    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[1]);
        add(A[1],1);
        max = A[1]; fs = 1; ls = 1;
        
        for (i = 2; i <= N; ++i)
          {
             scanf("%d",&A[i]);
             A[i] ^= A[i-1];
             add(A[i],i);
             find(A[i],i);
          }
          
        printf("%d %d %d",max,fs,ls);
        
        return 0;
    }