Cod sursa(job #185423)

Utilizator dgoldenAlex Popescu dgolden Data 25 aprilie 2008 12:48:46
Problema Xor Max Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.46 kb
type pnod = ^tnod;   
      tnod = record   
                poz : longint;   
                niv: shortint;   
                b:array[0..1] of pnod;   
                end;   
  
var xxor : array[0..100000] of longint;   
    n : longint;   
    head : pnod;   
    max, start,stop : longint;   
  
procedure updatetrie(nod : pnod;x,i:longint);   
var f: byte;   
    p: pnod;   
begin   
if nod^.niv = -1 then   
        nod^.poz:= i   
else   
        begin   
        if (1 shl nod^.niv) and x <> 0 then   
          f:=1 else f:=0;   
        if nod^.b[f] = nil then   
                begin   
                new(p); p^.niv:=nod^.niv-1; p^.b[0]:=nil; p^.b[1]:=nil; p^.poz:=0;   
                nod^.b[f]:=p;   
                end;   
        updatetrie(nod^.b[f],x,i);   
        end;   
end;   
  
procedure querytrie(nod:pnod; x,i:longint);   
var f : byte;   
begin   
if nod^.niv = -1 then   
        begin   
        if xxor[nod^.poz] xor xxor[i] > max then   
                begin   
                max:=xxor[nod^.poz] xor xxor[i];   
                if nod^.poz <> i then   
                start:=nod^.poz+1   
                else start:=nod^.poz;   
                stop:=i;   
                end   
{        else  
        if max = xxor[nod^.poz] xor xxor[i] then  
                if i - nod^.poz < stop - start then  
                        begin  
                        start:=nod^.poz + 1;  
                        stop:=i;  
                        end;}   
        end   
else   
         begin   
         if ( 1 shl nod^.niv) and x <> 0 then   
                f:=0 else f:=1;   
         if nod^.b[f] <> nil then   
                querytrie(nod^.b[f],x,i)   
         else querytrie(nod^.b[(f+1) mod 2],x,i);   
         end;   
end;   
  
  
  
procedure citirecalc;   
var i,v:longint;   
begin   
assign(input,'xormax.in'); reset(input);   
readln(n);   
xxor[0]:=0; updatetrie(head,xxor[0],-1);   
  
for i:=1 to n do   
        begin   
        read(v);   
        {if i > 1 then xxor[i]:=xxor[i-1] xor v  
        else}   
        xxor[i]:=xxor[i-1] xor v;   
        updatetrie(head,xxor[i],i);   
        querytrie(head,xxor[i],i)   
        end;   
end;   
  
begin   
max:=-1;   
new(head); head^.poz:=0; head^.niv:=20; head^.b[0]:=nil; head^.b[1]:=nil;   
citirecalc;   
assign(output,'xormax.out');rewrite(output);   
writeln(max,' ',start,' ',stop);   
close(output);   
end.