Cod sursa(job #5066)

Utilizator andrei_infoMirestean Andrei andrei_info Data 9 ianuarie 2007 22:18:05
Problema Xor Max Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.93 kb
//infoarena xormax var 2
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;
    nrb:byte;

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.