Собственно, данный пост ориентирован больше на новичков (большинство профессионалов с проблемой уже знакомы). Как известно, многие из тех, кто пишут quicksort вручную, попадались на anti-quicksort, и их решения получали TLE или, еще хуже, Stack Overflow. Явакодеров, казалось бы, эта проблема не касается: они пользуются стандартной функцией, которая, по идее, должна быть написана корректно. Не тут-то было... Короче, прилагаю исходник (лицензия GNU GPL 2 with Classpath exception, т.к. основан на исходном коде из OpenJDK). Запускать следует с параметром -Xss64m; сгенерированный массив выведется в файл.
P.S. Прошу прощения за ужасное качество исходника, выкладываю чисто для демонстрации. Более подробную информацию для интересующихся я добавлю потом.
UPD. Исправил ошибку с неправильным измерением времени сортировки.
Я сам хотел взломать Egor-а и Petr-аИ вместо того, чтобы прокачиваться и добиться своей мечты, ты запостил это. Великолепно.
месть ситховдень взломов на codeforces.Хотя этих топиков нет в английской версии сайта, так что можете попробовать оттянуться на наших "забугорных" товарищах если сильно охота.
Думаешь, AntiQuickSort - главная фишка? Поиски смешных вещей продолжаются.
Жалко, закончились времена компиляции на delphi7. У нее смешная бага в функции eoln, у кого есть, может проверить, что eoln() == false для позиции, кратной 0x80
Вот придумал человек как решить задачу.
Счастье просто переполняет, а тут "бац", и сиди, думай в чем проблема. И из-за времени, потраченного на поиск непонятно от куда берущегося бага человек лишился возможности получить опыт в решении других задач. Печаль, однако.
[trollface.jpg] Egor лишился возможности получить опыт.
Мы же не на детях это применять будем. Наша задача - tourist, Petr && ACRush 0.
Просто при подготовке одной из олимпиад в одном из тестов один из членов жюри выровнял пробелами по 32 символа файл, который надо было читать посимвольно. Он не хотел того, что получилось в итоге.
Для авторов, пишущих на делфи (слава Ктулху я уже писал на С++) это стало ужасной проблемой. Потом уже, имея на руках тест, я нашел косяк. Вот он:
function _Eoln(var t: TTextRec): Boolean; asm // -> EAX Pointer to text record // <- AL Boolean result CMP [EAX].TTextRec.Mode,fmInput JNE @@readChar MOV EDX,[EAX].TTextRec.BufPos CMP EDX,[EAX].TTextRec.BufEnd JAE @@readChar ADD EDX,[EAX].TTextRec.BufPtr TEST [EAX].TTextRec.Flags,tfCRLF [...] @@readChar: PUSH EAX CALL _ReadChar POP EDX CMP AH,cEOF JE @@eof DEC [EDX].TTextRec.BufPos XOR ECX,ECX XCHG ECX,EAX TEST [EDX].TTextRec.Mode,tfCRLF JNE @@testLF [...] end;Размер буфера 0x80. Можно заметить, что в случае отсутствия в буфере символа проверяется поле Mode вместо Flags, это дает всегда ответ false (там магия).
Мораль была, что можно использовать seekeoln.
Но вот во FreePascal-е функции seekX ведут себя не так, как в Delphi (причём документация об этом молчит): проверяют, что достигнут конец X, а потом, собаки, возвращают курсор обратно!