Cod sursa(job #779193)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 16 august 2012 23:05:15
Problema Xor Max Scor 85
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.15 kb
Program xormax;
 const len=20;
type trie=^celula;
     celula=record
       start:longint;
       sn:array ['0'..'1'] of trie;
       end;
var root:trie;
    a:array [0..100001] of longint;
    s,s1:string;
    str:ansistring;
    b1,b2:array [1..1 shl 17] of char;
    i,n,k,x,p1,max,p2,pos,aux,j: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') and (aux^.sn['1']<>nil) then aux:=aux^.sn['1']
    else if aux^.sn['0']<>nil then aux:=aux^.sn['0'];
  pos:=aux^.start;
end;

begin
 assign(fi,'xormax.in');
  assign(fo,'xormax.out');
 settextbuf(fi,b1); settextbuf(fo,b2);
  reset(fi); rewrite(fo); readln(fi,n); readln(fi,str); str:=str+' ';
   new(root); root^.sn['1']:=nil; root^.sn['0']:=nil; root^.start:=0;
    for i:=1 to len do s:=s+'0'; i:=0; insert; p1:=1; p2:=1; j:=1;
  for i:=1 to n do begin
                    x:=0; while str[j] in ['0'..'9'] do begin
                                                     x:=(x*10)+ord(str[j])-48;
                                                     inc(j);
                                                     end;
                     inc(j);
                    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:=s1+'0'; s:=s+'1'; end else begin s1:=s1+'1'; s:=s+'0'; end;
                      aux:=aux shr 1;
                     end;
                     cauta;
                    insert;
                    if a[i] xor a[pos]>max then begin max:=a[i] xor a[pos]; p1:=pos+1; p2:=i; end;
                   end;
  write(fo,max,' ',p1,' ',p2);
 close(fo);
end.