|
|
|
|
|
|
|
| 21 Трохачев Андрей Вадимович, 29 октября 2019 г. 0:17:13 |
| У кого TL на 11 тесте на C++, допишите в начало вот это: ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); Так проходит за 0.8 секунд даже с реализацией через сортировку за O(nlogn).
|
|
|
| 22 Егоров Илья Валерьевич, 24 августа 2019 г. 4:38:16 |
| iostream долгий из-за, во-первых, синхронизации с stdio, а, во-вторых, из-за нацела на абстрактности источника. Синхронизация как древний костыль, возникший в силу смешивания stdio и iostream: даже если вы их оба не используете одновременно, лишние действия все равно будут, поэтому следует явно отключать синхронизацию при желании. Абстрактность источника же — это сила "использовать один и тот же интерфейс как для ФС, так и для сети и всего прочего". Следствием стало построение ввода-вывода на неком ограниченном наборе функций, что дает еще одно следствие: это неэффективно. В то время, как мы могли бы определить очень-очень быструю функцию для считывания конкретно знаковых целочисленных типов, iostream абстрагируется от источника, использует набор заготовленных функций, делает уйму проверок, да еще и используется преимущественно для ввода-вывода объектов. Лучший путь — написать свой велосипед поверх чего-то вроде fread, затем сослаться на plan9-way "всё есть файл", но прод будет против.
|
|
|
| 23 Матвеев Роман Николаевич, 22 августа 2019 г. 21:25:04 |
| Использовал cin и cout для ввода и вывода, на 11 тесте время больше 2-ух секунд. Удалил строчку #include <iostream> и использовал stdio.h, все прошло. Почему из-за <iostream> программа работает так долго?
|
|
|
| 24 Егоров Илья Валерьевич, 01 июня 2019 г. 19:53:13 |
| Достаточно (да оно почти везде достаточно, т.к. ограничения по памяти слишком безобидные), но не эффективно.
|
|
|
| 25 Сулейманов Тимур Олегович, 30 мая 2019 г. 13:46:30 |
| На Python достаточно использовать встроенную функцию sorted() и вывод с помощью цикла for.
|
|
|
| 26 Егоров Илья Валерьевич, 21 марта 2019 г. 12:27:45 |
| [Тоже Java] Код переписан под Java API, реализованы [Input/Output]Stream-обертки для MappedByteBuffer, свой UnsafeReader (интерфейс, имеются реализации: RawReader для InputStream и PrintReader для Reader). Несмотря на излишне богатый функционал (в частности, предоставляемый default методами UnsafeReader, который работает не через регулярки как Scanner, а через вызовы read()), с помощью небольшого хака (для MappedInputStream), связывающего методы чтения чисел с ByteBuffer напрямую, удалось приблизить результаты по времени к 0.103, а также еще сильнее сэкономить память. Также выяснилось, что приделать BufferedOutputStream к MappedOutputStream — это действительно хорошая мысль (для данных условий).
|
|
|
| 27 Егоров Илья Валерьевич, 19 марта 2019 г. 22:08:45 |
| [На Java] С помощью генерации побочных массивов в рантайме, а также с выделением кастомной системы ввода-вывода в отдельный класс, удалось минимизировать потери по памяти и свести время к относительно стабильному 0.118. Дальнейшие оптимизации все еще, как предполагается, возможны.
|
|
|
| 28 Егоров Илья Валерьевич, 19 марта 2019 г. 4:28:36 |
| На Java использование модифицированного вывода с ручным парсингом в сишном стиле может выдать 0.15 сек. Замена BufferedReader на MappedByteBuffer в ущерб памяти позволяет достичь 0.103 сек. по времени (при наиболее благоприятных обстоятельствах). Гипотетически возможны дальнейшие оптимизации
|
|
|
| 29 Мальков Виктор Александрович, 27 февраля 2019 г. 22:58:53 |
| На Python основное время тратится не на саму сортировку, а на вывод. Попробуйте его реализовать так print(str((ar[i]) + ' ') * ar[i]). Такой вывод мне помог. Умножение строки пооисходит гораздо быстрее посимвольного вывода
|
|
|
| 30 Ринчинов Солбон Геннадьевич, 06 января 2019 г. 21:57:08 |
| На Java самодельный ввод/вывод == 0.196 сек
|
|
|
| 31 Слива Лиловая Спелая Садовая, 06 декабря 2018 г. 18:35:46 |
| Для тех, кто пишет на Си: прочитайте про функцию qsort
|
|
|
| 32 Егоров Илья Валерьевич, 05 ноября 2018 г. 18:50:58 |
| А если использовать fread(_nolock) и fwrite(_nolock), можно дожать и до 0.015
|
|
|
| 33 Ринчинов Солбон Геннадьевич, 02 ноября 2018 г. 22:07:54 |
| Можно воспользоваться getchar и putchar для вывода. Это позволит улучшить время до 0.7 сек. Если использовать _getchar_nolock и _putchar_nolock, то можно улучшить (зависит от реализации) до 0.5 - 0.092.
|
|
|
| 34 Денисов Давид Юрьевич, 05 сентября 2018 г. 12:02:25 |
Сдал двумя способами: сортировкой подсчётом, и затем для проверки функцией sort из С++, на некоторых тестах была быстрее сортировка подсчётом, на некоторых sort, но итоговое время у них получилось одинаковое, почему так, если у сортировки подсчётом асимптотическая сложность должна быть куда лучше?
Попробуйте сдать каждое из решений по 10 раз и посмотрите на распределение времени работы. Возможно при одном запуске была флуктуация. Так-то конечно вариант с std::sort должен дольше работать, хотя бы на 0.05 секунды.
|
|
|
| 35 Федоров Иван Денисович, 05 августа 2018 г. 1:13:47 |
| У кого на джаве TL, советую вводить через StreamTokenizer и выводить через PrintWriter
|
|
|
| 36 Артур Муравленко-ЯНАО, 29 июля 2018 г. 18:08:07 |
| PascalABC.NET стало чуть быстрее - 1.5 секунд.
|
|
|
| 37 Городецкий Евгений Леонидович, 07 мая 2018 г. 19:54:03 |
Сдал c первой попытки на FPC. Попробовал этот же код на PABC - time limit, хотя у меня проходит за 0,8 секунд. Быстрая сортировка PABC - тоже time limit, хотя у меня 0,9 секунд.
Попробуйте работать не с консолью, а с файлами input.txt и output.txt. На Pascal ABC это помогает ускорить ввод и вывод.
|
|
|
| 38 Егоров Илья Валерьевич, 13 апреля 2018 г. 23:44:39 |
| Аллилуйя! Добил до 0.03 (решение №8188211). Теперь бы так и 224. P.s. Для тех, у кого по каким-то причинам не проходит по времени, или же кто тоже заинтересован в оптимизации, в обсуждении 224 описаны некоторые моменты. И небольшая поправка: своя реализация вывода чисел через fwrite всё же быстрее, чем printf
|
|
|
| 39 Кияко Вячеслав Вячеславович, 21 марта 2018 г. 22:24:37 |
Получилось сдать задачу только после замены iostream на stdio.h
Кроме того, в gcc заголовочный файл stdio.h должен стоять первым, чтобы было ускорение.
|
|
|
| 40 Артур Муравленко-ЯНАО, 17 февраля 2018 г. 21:26:54 |
PascalABC.NET - все работает. 1.7 сек
С условием чтения из файла и вывод в файл.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
