Обсуждение @ 1613. Для любителей статистики @ Timus Online Judge

ACSpeed For WA4 or WA6 [2] // Задача 1613. Для любителей статистики 22 ноя 2011 22:12

I find it very strange when in QuickSort :

pivot = A[(High+Low) div 2]; will get me AC for both tests

while

pivot = (High+Low) div 2;
....
A[pivot] will give me WA4/WA6 .

MOPDOBOPOT (USU) Re: For WA4 or WA6 // Задача 1613. Для любителей статистики 30 июл 2012 21:05

Try to sort this array (it's too big, but i'm so lazy and don't want to discover another example) with second version of your qSort:

16
4 2 3 2 2 1 2 10 6 3 2 2 11 128 0 2

What you got? :)

Edited by author 30.07.2012 21:12

DR. Zhihua Lai Re: For WA4 or WA6 // Задача 1613. Для любителей статистики 2 дек 2012 03:35

    pp := arr[(ll + rr) div 2].val;
    while (ii <= jj) do
    begin
      while (arr[ii].val < pp) do Inc(ii);
      while (arr[jj].val > pp) do Dec(jj);
      if (ii <= jj) then
      begin
        t := arr[ii];
        arr[ii] := arr[jj];
        arr[jj] := t;
        Inc(ii);
        Dec(jj);
      end;
    end;

This is right. but not this
    pp := (ll + rr) div 2;
    while (ii <= jj) do
    begin
      while (arr[ii].val < arr[pp].val) do Inc(ii);
      while (arr[jj].val > arr[pp].val) do Dec(jj);
      if (ii <= jj) then
      begin
        t := arr[ii];
        arr[ii] := arr[jj];
        arr[jj] := t;
        Inc(ii);
        Dec(jj);
      end;
    end;

because in the loop, the if statement will possibly change the value of arr[pp].val.
That is why you have WA6.

Обсуждение задачи 1613. Для любителей статистики