Cod sursa(job #849238)

Utilizator t.g.g.tt.g.g.t t.g.g.t Data 6 ianuarie 2013 19:07:47
Problema Xor Max Scor 50
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.93 kb
type tri=^celula;
     celula=record
       i:longint;
       a:array['0'..'1']of tri;
     end;
var a:array[0..100000]of longint; buf1:array[1..1 shl 17]of char; s:string;
i,n,v,r1,r2,j,max,l,sol:longint; trie:tri; p:pointer;
begin
new(trie); p:=trie; trie^.i:=0; trie^.a['0']:=nil; trie^.a['1']:=nil;
assign(input,'xormax.in'); reset(input); settextbuf(input,buf1);  r1:=1; r2:=1;
readln(n);
for i:=1 to n do
  begin
    read(v);
    if sol<v then begin sol:=v; r1:=i; r2:=i end;
    if i=1 then begin maX:=v; sol:=v end;
    a[i]:=v xor a[i-1];
    if a[i]>max then begin max:=a[i]; end;
  end;
while max<>0 do begin s:=chr((max mod 2)+48)+s; max:=max div 2; end;
max:=length(s);s:='';
v:=a[1];
while v<>0 do begin s:=chr((v mod 2)+48)+s; v:=v div 2; end;
l:=length(s);
for j:=1 to max-l do s:='0'+s;
j:=1; l:=length(s);
while j<=l do begin new(trie^.a[s[j]]); trie:=trie^.a[s[j]]; trie^.i:=0; trie^.a['0']:=nil; trie^.a['1']:=nil; inc(j); end;
trie^.i:=1; trie:=p;
for i:=2 to n do
  begin
    s:='';
    v:=a[i];
    while v<>0 do begin s:=chr((v mod 2)+48)+s; v:=v div 2; end;
    l:=length(s);
    for j:=1 to max-l do s:='0'+s;
    j:=1;
    while j<=max do
      begin
        if s[j]='0' then if trie^.a['1']<>nil then trie:=trie^.a['1'] else trie:=trie^.a['0'];
        if s[j]='1' then if trie^.a['0']<>nil then trie:=trie^.a['0'] else trie:=trie^.a['1'];
        inc(j);
      end;
    if (sol<a[i]) then begin sol:=a[i]; r1:=1; r2:=i end;
    if (sol<(a[i] xor a[trie^.i])) then begin r1:=trie^.i+1; r2:=i; sol:=a[i] xor a[trie^.i] end;
    trie:=p; j:=1;
    while j<=max do
      begin
        if trie^.a[s[j]]=nil then begin new(trie^.a[s[j]]); trie:=trie^.a[s[j]]; trie^.i:=0; trie^.a['0']:=nil; trie^.a['1']:=nil; end else trie:=trie^.a[s[j]];
        inc(j);
      end;
    trie^.i:=i; trie:=p;
  end;
assign(output,'xormax.out'); rewrite(output);
writeln(sol,' ',r1,' ',r2);
close(output);
end.