Запихиваем O(N^2) для N=2·10^5 в Edu131 F

Правка ru3, от qwerty787788, 2022-07-11 13:05:08

Я часто видел как в задачах кто-то сдавал простое решение за $$$O(n^2)$$$, хотя авторы этого явно не хотели. Обычно секрет в том, чтобы писать код, который хорошо векторизуется (использует всякие SIMD инструкции), но без опыта делать это получается плохо, потому что нет интуиции, что будет работать быстро, а что нет.

Когда я увидел задачу 1701F - Точки и TL=6.5с решил, что это отличный шанс с одной стороны написать решение за квадрат, которое получит AC, а с другой — записать сам процесс оптимизации кода, вдруг кому-то будет интересно.

Получилась вот такая статья. Там довольно много вещей, которые специфичны только для Rust, но я думаю, что в С++ есть аналогичные проблемы/решения.

А еще подписывайтесь на мой канал в Telegram, чтобы у меня была мотивация писать что-то еще. Там скорее всего будет не только про олимпиады, а в целом про программирование.

P.S. надеюсь на CF не банят за саморекламу :)

Теги simd, оптимизации

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru3 Русский qwerty787788 2022-07-11 13:05:08 0 (опубликовано)
ru2 Русский qwerty787788 2022-07-11 12:59:46 37
ru1 Русский qwerty787788 2022-07-11 12:57:39 1155 Первая редакция (сохранено в черновиках)