Cod sursa(job #849373)

Utilizator t.g.g.tt.g.g.t t.g.g.t Data 6 ianuarie 2013 20:48:18
Problema Xor Max Scor 55
Compilator fpc Status done
Runda Arhiva de probleme Marime 2 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,j2:longint; trie:tri; p:pointer; s2:ansistring;
begin
new(trie); p:=trie; trie^.a['0']:=nil; trie^.a['1']:=nil;
assign(input,'xormax.in'); reset(input); settextbuf(input,buf1);
readln(n);
max:=21;
read(s2);  s2:=s2+' ';
j2:=1; while s2[j2]<>' ' do begin a[1]:=a[1]*10+ord(s2[j2])-48; inc(j2); end; inc(j2);
v:=a[1];
while v<>0 do begin s:=chr((v mod 2)+48)+s; v:=v div 2; end;
l:=length(s); l:=max-l;
for j:=1 to l do s:='0'+s;
j:=1; sol:=a[1]; r1:=1; r2:=1;
while j<=max do begin new(trie^.a[s[j]]); trie:=trie^.a[s[j]]; trie^.a['0']:=nil; trie^.a['1']:=nil; inc(j); end;
trie^.i:=1; trie:=p;
for i:=2 to n do
  begin
    v:=0; while s2[j2]<>' ' do begin v:=v*10+ord(s2[j2])-48; inc(j2); end; inc(j2);
    a[i]:=v xor a[i-1];
    s:='';
    v:=a[i];
    while v<>0 do begin if v and 1 =1 then s:='1'+s else s:='0'+s; v:=v shr 1; end;
    l:=length(s); l:=max-l;
    for j:=1 to 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;
    if (sol=(a[i] xor a[trie^.i])) then if (r1<=trie^.i+1) and (r2>=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^.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.