MYTURN.PAS 3.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129
  1. const Len=181; {181 ~= Sqrt(32767)}
  2. Block=32767 div Len;
  3. type Ppp=array[0..Len-1] of longint;
  4. var LL,A,B:array[0..Block] of ^Ppp;
  5. L:Array[1..33000] of boolean;
  6. V:array[1..Block+1] of boolean;
  7. C:array[1..Block+1,1..2] of longint;
  8. ga,gb,q,i,j,k,n,t:longint;
  9. E,S,P:longint;
  10. procedure Merge(p,q:longint);
  11. var i,d,c,i1,i2:longint;
  12. begin
  13. if p>=q then exit;
  14. c:=(p+q) div 2;
  15. Merge(p,c);
  16. Merge(c+1,q);
  17. i1:=p;
  18. i2:=c+1;
  19. d:=p;
  20. while (i1<=c)and(i2<=q) do
  21. if B[i1 div Len]^[i1 mod Len]<B[i2 div Len]^[i2 mod Len] then begin
  22. LL[d div Len]^[d mod Len]:=B[i1 div Len]^[i1 mod Len];
  23. inc(i1);inc(d);
  24. end
  25. else begin
  26. LL[d div Len]^[d mod Len]:=B[i2 div Len]^[i2 mod Len];
  27. inc(i2);inc(d);
  28. end;
  29. while (i1<=c) do begin
  30. LL[d div Len]^[d mod Len]:=B[i1 div Len]^[i1 mod Len];
  31. inc(i1);inc(d);
  32. end;
  33. while (i2<=q) do begin
  34. LL[d div Len]^[d mod Len]:=B[i2 div Len]^[i2 mod Len];
  35. inc(i2);inc(d);
  36. end;
  37. for i:=p to q do B[i div Len]^[i mod Len]:=LL[i div Len]^[i mod Len];
  38. end;
  39. function Search(c:longint):word;
  40. var p,q:longint;
  41. g:word;
  42. begin
  43. p:=1;q:=n;
  44. g:=(p+q) div 2;
  45. while c<>B[g div Len]^[g mod Len] do begin
  46. if c>B[g div Len]^[g mod Len] then p:=g+1
  47. else q:=g-1;
  48. g:=(p+q) div 2;
  49. end;
  50. Search:=g;
  51. end;
  52. begin
  53. assign(input,'turnover.in');reset(input);
  54. assign(output,'turnover.out');rewrite(output);
  55. read(n);
  56. for i:=0 to Block do begin
  57. new(A[i]);
  58. fillchar(A[i]^,sizeof(A[i]^),0);
  59. end;
  60. for i:=0 to Block do new(B[i]);
  61. for i:=0 to Block do new(LL[i]);
  62. for i:=1 to n do read(A[i div Len]^[i mod Len]);
  63. for i:=0 to Block do B[i]^:=A[i]^;
  64. Merge(1,n);
  65. fillchar(l,sizeof(l),false);
  66. fillchar(v,sizeof(v),false);
  67. for i:=1 to Block+1 do begin
  68. C[i,1]:=i*Len;
  69. C[i,2]:=(i-1)*Len+1;
  70. if C[i,1]>n then C[i,1]:=n;
  71. if C[i,2]>n then C[i,2]:=n;
  72. end;
  73. s:=0;
  74. for i:=1 to n do begin
  75. P:=A[i div Len]^[i mod Len];
  76. q:=Search(P);
  77. k:=(q-1) div Len+1;
  78. ga:=0;gb:=0;
  79. if V[k] then begin
  80. j:=q;
  81. while j>=C[k,1] do begin
  82. if L[j] then break;
  83. dec(j);
  84. end;
  85. if j>=C[k,1] then gb:=j;
  86. j:=q;
  87. while j<=C[k,2] do begin
  88. if L[j] then break;
  89. inc(j);
  90. end;
  91. if j<=C[k,2] then ga:=j;
  92. end;
  93. if ga=0 then begin
  94. t:=k+1;
  95. while t<=(n-1) div Len+1 do begin
  96. if V[t] then break;
  97. inc(t);
  98. end;
  99. if t<=(n-1) div Len+1 then begin
  100. j:=C[t,1];
  101. ga:=j;
  102. end;
  103. end;
  104. if gb=0 then begin
  105. t:=k-1;
  106. while t>0 do begin
  107. if V[t] then break;
  108. dec(t);
  109. end;
  110. if t>0 then begin
  111. j:=C[t,2];
  112. gb:=j;
  113. end;
  114. end;
  115. E:=maxlongint;
  116. if (ga=0)and(gb=0) then E:=abs(p);
  117. if ga<>0 then if abs(p-B[ga div Len]^[ga mod Len])<E then
  118. E:=abs(p-B[ga div Len]^[ga mod Len]);
  119. if gb<>0 then if abs(p-B[gb div Len]^[gb mod Len])<E then
  120. E:=abs(p-B[gb div Len]^[gb mod Len]);
  121. V[k]:=true;
  122. L[q]:=true;
  123. if q<C[k,1] then C[k,1]:=q;
  124. if q>C[k,2] then C[k,2]:=q;
  125. S:=S+E;
  126. end;
  127. writeln(S);
  128. close(input);close(output);
  129. end.