Cod sursa(job #849339)

Utilizator t.g.g.tt.g.g.t t.g.g.t Data 6 ianuarie 2013 20:03:19
Problema Xor Max Scor 50
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.85 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);
max:=23;s:='';
read(a[1]);
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); sol:=a[1]; r1:=1; r2:=1;
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
    read(v); a[i]:=v xor a[i-1];
    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;
    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^.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.