Дистанционная подготовка: и все-таки порядок важен
и все-таки порядок важен
от Тимофей Сафронов - Суббота 1 Декабрь 2018, 20:29
414. Эльфы и олени
  итак
почему же я так решил?
написав решение по разбору, обнаружил что посылка прошла лишь 13 тестов
хм
я сделал незначительные изменения
которые не могли ничего изменить
но
теперь 14 тестов
ещё раз
теперь 15
и ещё раз
теперь 17
ещё раз
16
то есть
один и тот же код
проходит разное колво тестов
я начал внимательно анализировать программу
на предмет выхода за границу массива и неправильно е использование рандома
массивы по 100000
опорную точку в сортировке быстрой(l,r - границы)
я выбираю по формуле p=a[rand()%(r-l+1)+l]
все правильно
хм
переставил при выводе двух эльфов
printf("%d %d %d\n",a[j][1],b[i][1],b[n-k+i][1]);
заменил на
printf("%d %d %d\n",a[j][1],b[n-k+i][1],b[i][1]);
6 тестов
итог - порядок важен
Re: и все-таки порядок важен
от Тимофей Сафронов - Суббота 1 Декабрь 2018, 21:00
  также
я заменил случайный выбор пивота в быстрой сортировке на выбор среднего
итог - стабильные 14 тестов
но почему?
потому что быстрая сортировка моя неустойчивая
то есть может изменить порядок одинаковых элементов относительно друг друга
и вот что получается
сортировка то происходит
но равные элементы при каждом запуске имеют разные номера
поэтому колво тестов проходит разное
но ведь нету разницы какого из двух одинаковых эльфов я выберу

админ проверь чекер задачи
или пожалуйста ткни меня носом в ошибку
Re: и все-таки порядок важен
от Тимофей Сафронов - Суббота 1 Декабрь 2018, 20:52
  или киньте кто своё решение задачи
особенно если оно на c++
Re: и все-таки порядок важен
от Тимофей Сафронов - Суббота 1 Декабрь 2018, 22:05
  опять здравствуйте
я переписал программу
с использованием sortов из stl
и что вы думаете произошло?
именно
произошел OK
Re: и все-таки порядок важен
от Тимофей Сафронов - Суббота 1 Декабрь 2018, 22:49
  .....
все в порядке
в быстрой сортировке был очень хитрый косяк с указателем...