Cod sursa(job #849602)

Utilizator t.g.g.tt.g.g.t t.g.g.t Data 7 ianuarie 2013 13:01:34
Problema Xor Max Scor 25
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.95 kb
type tri=^celula;
     celula=record
       i:longint;
       a:array['0'..'1']of tri;
     end;
var a:array[0..100000]of longint;  n,j,v,i,j2,l,sol,r1,r2:longint; s:ansistring; s2:array[0..21]of char;
trie:tri; p:pointer; buf1:array[1..1 shl 17]of char;
begin
new(trie); trie^.a['1']:=nil; trie^.a['0']:=nil; p:=trie;
assign(input,'xormax.in'); reset(input); settextbuf(input,buf1);
readln(n); readln(s); j:=1; v:=0;  s:=s+' ';
for i:=1 to 21 do begin new(trie^.a['0']); trie:=trie^.a['0']; trie^.a['0']:=nil; trie^.a['1']:=nil; s2[i]:='0' end; trie^.i:=0; trie:=p;
while s[j]<>' ' do begin v:=v*10+ord(s[j])-48; inc(j); end; inc(j);
a[1]:=v; l:=21;
while v<>0 do begin if v and 1=1 then s2[l]:='1' else s2[l]:='0'; dec(l); v:=v shr 1; end;
for i:=1 to 21 do begin if trie^.a[s2[i]]=nil then begin new(trie^.a[s2[i]]); trie:=trie^.a[s2[i]]; trie^.a['0']:=nil; trie^.a['1']:=nil end else trie:=trie^.a[s2[i]]; s2[i]:='0' end;
trie^.i:=1; trie:=p; sol:=a[1]; r1:=1; r2:=1;
for i:=2 to n do
  begin
    v:=0;
    while s[j]<>' ' do begin v:=v*10+ord(s[j])-48; inc(j); end; inc(j);
    a[i]:=v xor a[i-1]; v:=a[i]; l:=21;
    while v<>0 do begin if v and 1=1 then s2[l]:='1' else s2[l]:='0'; dec(l); v:=v shr 1; end;
    for j2:=1 to 21 do
      begin
        if s2[j2]='1' then begin if trie^.a['0']<>nil then trie:=trie^.a['0'] else trie:=trie^.a['1'] end
                      else begin if trie^.a['1']<>nil then trie:=trie^.a['1'] else trie:=trie^.a['0'] end;
      end;
    if sol<a[i] xor a[trie^.i] then begin sol:=a[i] xor a[trie^.i]; r1:=trie^.i+1; r2:=i;  end;
    trie:=p;
    for j2:=1 to 21 do
      begin
        if trie^.a[s2[j2]]=nil then begin new(trie^.a[s2[j2]]); trie:=trie^.a[s2[j2]]; trie^.a['0']:=nil; trie^.a['1']:=nil; s2[j2]:='0' end
                               else trie:=trie^.a[s2[j2]]
      end;
    trie^.i:=i; trie:=p;
  end;
assign(output,'xormax.out'); rewrite(output);
writeln(sol,' ',r1,' ',r2);
close(output);
end.