Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Вернуться к задаче]   1 2
  1  Егоров Илья Валерьевич, 01 июня 2019 г. 19:53:13
     Достаточно (да оно почти везде достаточно, т.к. ограничения по памяти слишком безобидные), но не эффективно.
  2  Сулейманов Тимур Олегович, 30 мая 2019 г. 13:46:30
     На Python достаточно использовать встроенную функцию sorted() и вывод с помощью цикла for.
  3  Егоров Илья Валерьевич, 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 — это действительно хорошая мысль (для данных условий).
  4  Егоров Илья Валерьевич, 19 марта 2019 г. 22:08:45
     [На Java] С помощью генерации побочных массивов в рантайме, а также с выделением кастомной системы ввода-вывода в отдельный класс, удалось минимизировать потери по памяти и свести время к относительно стабильному 0.118. Дальнейшие оптимизации все еще, как предполагается, возможны.
  5  Егоров Илья Валерьевич, 19 марта 2019 г. 4:28:36
     На Java использование модифицированного вывода с ручным парсингом в сишном стиле может выдать 0.15 сек. Замена BufferedReader на MappedByteBuffer в ущерб памяти позволяет достичь 0.103 сек. по времени (при наиболее благоприятных обстоятельствах). Гипотетически возможны дальнейшие оптимизации
  6  Мальков Виктор Александрович, 27 февраля 2019 г. 22:58:53
     На Python основное время тратится не на саму сортировку, а на вывод. Попробуйте его реализовать так print(str((ar[i]) + ' ') * ar[i]). Такой вывод мне помог. Умножение строки пооисходит гораздо быстрее посимвольного вывода
  7  Ринчинов Солбон Геннадьевич, 06 января 2019 г. 21:57:08
     На Java самодельный ввод/вывод == 0.196 сек
  8  Слива Лиловая Спелая Садовая, 06 декабря 2018 г. 18:35:46
     Для тех, кто пишет на Си: прочитайте про функцию qsort
  9  Егоров Илья Валерьевич, 05 ноября 2018 г. 18:50:58
     А если использовать fread(_nolock) и fwrite(_nolock), можно дожать и до 0.015
  10  Ринчинов Солбон Геннадьевич, 02 ноября 2018 г. 22:07:54
     Можно воспользоваться getchar и putchar для вывода. Это позволит улучшить время до 0.7 сек. Если использовать _getchar_nolock и _putchar_nolock, то можно улучшить (зависит от реализации) до 0.5 - 0.092.
  11  Денисов Давид Юрьевич, 05 сентября 2018 г. 12:02:25
     Сдал двумя способами: сортировкой подсчётом, и затем для проверки функцией sort из С++, на некоторых тестах была быстрее сортировка подсчётом, на некоторых sort, но итоговое время у них получилось одинаковое, почему так, если у сортировки подсчётом асимптотическая сложность должна быть куда лучше?
     Попробуйте сдать каждое из решений по 10 раз и посмотрите на распределение времени работы. Возможно при одном запуске была флуктуация. Так-то конечно вариант с std::sort должен дольше работать, хотя бы на 0.05 секунды.
  12  Федоров Иван Денисович, 05 августа 2018 г. 1:13:47
     У кого на джаве TL, советую вводить через StreamTokenizer и выводить через PrintWriter
  13  Артур Муравленко-ЯНАО, 29 июля 2018 г. 18:08:07
     PascalABC.NET стало чуть быстрее - 1.5 секунд.
  14  Городецкий Евгений Леонидович, 07 мая 2018 г. 19:54:03
     Сдал c первой попытки на FPC. Попробовал этот же код на PABC - time limit, хотя у меня проходит за 0,8 секунд. Быстрая сортировка PABC - тоже time limit, хотя у меня 0,9 секунд.
     Попробуйте работать не с консолью, а с файлами input.txt и output.txt. На Pascal ABC это помогает ускорить ввод и вывод.
  15  Егоров Илья Валерьевич, 13 апреля 2018 г. 23:44:39
     Аллилуйя! Добил до 0.03 (решение №8188211). Теперь бы так и 224. P.s. Для тех, у кого по каким-то причинам не проходит по времени, или же кто тоже заинтересован в оптимизации, в обсуждении 224 описаны некоторые моменты. И небольшая поправка: своя реализация вывода чисел через fwrite всё же быстрее, чем printf
  16  Кияко Вячеслав Вячеславович, 21 марта 2018 г. 22:24:37
     Получилось сдать задачу только после замены iostream на stdio.h
     Кроме того, в gcc заголовочный файл stdio.h должен стоять первым, чтобы было ускорение.
  17  Артур Муравленко-ЯНАО, 17 февраля 2018 г. 21:26:54
     PascalABC.NET - все работает. 1.7 сек
     С условием чтения из файла и вывод в файл.
  18  Далецкий Андрей два, 30 января 2018 г. 14:28:21
     Если вы учли всё, но никак не обойти тайм лимит--убирайте все лишние библиотеки
     На gcc достаточно первым заголовочным файлом поставить stdio.h.
  19  Борисов Евгений Александрович, 12 января 2018 г. 9:30:17
     Программа считывающая с диска и записывающая на диск 1 миллион чисел (3,4 Мб) на локальном компьютере выполняется за 0,65 сек, сам подсчёт - менее 0,25 сек. 11 тест на проверочной машине не укладывается в 2 секунды. В 20-ке решений на Паскале - ни одного на Pascal ABC, при том что на других задачах из Паскалей преобладает именно Pascal ABC. Это такой специальный унизительный тест, замедляющий файловые операции для Pascal ABC?
  20  Литвиненко Михаил Максимович, 06 декабря 2017 г. 13:23:17
     короче, здесь работает спокойно за секунду sort(algorithm), qsort(cstdlib),сортировка подсчетом(wiki ;)
если у вас не проходит по времени, то юзайте stdio.h и удалите строчку с #include <iostream>
даже если не использовать iostream, время почему-то зашкаливает
Удачи
 1 2

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru