Cod sursa(job #213328)

Utilizator theratmantheratman theratman Data 9 octombrie 2008 14:30:43
Problema Xor Max Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.96 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
         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);
         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.