Cod sursa(job #5039)

Utilizator andrei_infoMirestean Andrei andrei_info Data 9 ianuarie 2007 21:18:27
Problema Xor Max Scor 40
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.09 kb
//infoarena xormax var 2

type pnod = ^tnod;
      tnod = record
                poz : longint;
                niv: shortint;
                b:array[0..1] of pnod;
                end;

var xxor : array[1..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];
                start:=nod^.poz+1;
                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);


for i:=1 to n do
        begin
        read(v);
        if i > 1 then xxor[i]:=xxor[i-1] xor v
        else xxor[i]:=v;
        updatetrie(head,xxor[i],i);
        querytrie(head,xxor[i],i)
        end;
end;

begin
new(head); head^.poz:=0; head^.niv:=22; head^.b[0]:=nil; head^.b[1]:=nil;
citirecalc;
assign(output,'xormax.out');rewrite(output);
writeln(max,' ',start,' ',stop);
close(output);
end.