Cod sursa(job #779171)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 16 august 2012 22:11:36
Problema Xor Max Scor 15
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.78 kb
Program xormax;
 const len=22;
type trie=^celula;
     celula=record
       start:longint;
       sn:array ['0'..'1'] of trie;
       end;
var root:trie;
    a:array [0..100001] of integer;
    s,s1:string;
    i,n,k,x,p1,max,p2,pos,aux:longint;
    fi,fo:text;

procedure insert;
 var aux:trie;
      k:integer;
begin
 aux:=root;
  for k:=1 to length(s) do
   if aux^.sn[s[k]]=nil then begin
                              new(aux^.sn[s[k]]);
                               aux:=aux^.sn[s[k]];
                               aux^.sn['0']:=nil; aux^.sn['1']:=nil;
                              end
   else aux:=aux^.sn[s[k]];
 aux^.start:=i;
end;

procedure cauta;
 var aux:trie;
     k:integer;
begin
 aux:=root;
  for k:=1 to length(s1) do
   if aux^.sn[s1[k]]<>nil then aux:=aux^.sn[s1[k]]
   else if s1[k]='0' then aux:=aux^.sn['1']
    else aux:=aux^.sn['0'];
 pos:=aux^.start;
end;

begin
 assign(fi,'xormax.in');
  assign(fo,'xormax.out');
  reset(fi); rewrite(fo); readln(fi,n);
   new(root); root^.sn['1']:=nil; root^.sn['0']:=nil;
    for i:=1 to len do s:=s+'0'; i:=0; insert;
  for i:=1 to n do begin
                    read(fi,x);
                    a[i]:=x xor a[i-1]; aux:=a[i]; s:=''; s1:='';
                    for k:=1 to len do begin
                     if aux and 1=1 then begin s1:='0'+s1; s:='1'+s; end else begin s1:='1'+s1; s:='0'+s; end;
                      aux:=aux shr 1;
                     end;
                    insert;
                    cauta;
                    if a[i] xor a[pos]>max then begin max:=a[i] xor a[pos]; p1:=pos+1; p2:=i; end
                    else if (a[i] xor a[pos]=max) and (i-pos<p2-p1+1) then begin p2:=i; p1:=pos+1; end;
                   end;
  write(fo,max,' ',p1,' ',p2);
 close(fo);
end.