ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

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

For WA4 or WA6
Послано ACSpeed 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 .
Re: For WA4 or WA6
Послано MOPDOBOPOT (USU) 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
Re: For WA4 or WA6
Послано DR. Zhihua Lai 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.