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

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

HotLog


 
[Вернуться к задаче]   1 2 3
  1  Егоров Илья Валерьевич, 25 января 2020 г. 20:34:10
     С таким же успехом можно использовать int64_t (или любые другие два *64_t) из stdint.h, который появился в том же стандарте (C99), что и long long int. Так или иначе, все это упоминалось в ранних сообщениях обсуждения этой задачи, которые почему-то, судя по появлению новых, не особо много кто и читает. Так что совет всем тем, у кого те или иные проблемы с задачей: читайте предыдущие сообщения, их тут на данный момент 3 страницы. Там даже есть те, которые явно намекают на эффективный алгоритм решения задачи, а про обход ограничений и так полно (включая и мои собственные, разве что тут не описаны последние усовершенствования решения на плюсах).
  2  Чопонов Данияр Болотович, 25 января 2020 г. 5:29:17
     22 тесте выше 10^6 для с++ long long в помощь:))
  3  Егоров Илья Валерьевич, 23 января 2020 г. 18:10:39
     Тьфу. *чуть больше мегабайта памяти: с привыканием к Linux API привыкаешь и к байтам в качестве единиц измерения.
  4  Егоров Илья Валерьевич, 23 января 2020 г. 17:49:29
     ...поскольку тут лишь сказано как числа считывать, но нет и намека на алгоритм решения заданной задачи.
  5  Егоров Илья Валерьевич, 23 января 2020 г. 17:49:06
     Открыть файл можно так (не забыв сделать import os, mmap): m = mmap.mmap(os.open('INPUT.TXT', os.O_RDONLY), 0, access = mmap.ACCESS_READ). Считать N можно так: n = 0; c = m.read_byte(); while c > 32:; ~~n = n * 10 + c - 48; ~~c = m.read_byte(); m.read_byte(), где ; обозначает новую строку, а ~~ — отступ. c > 32 проверяет, что код символа больше пробела, что соответствует видимым символам вроде цифр, но не соответствует пробелу, переводу строки, управляющим символам и т.п. 48 — код символа нуля, т.е., например, ord('5') - 48 = 5: так парсим цифры, а цикл строит из цифр число. Последний m.read_byte() нужен только для игнорирования символа возврата каретки, ибо тесты проверяющей системы в стиле винды: \n\r в качестве новой строки. В таком же духе можно парсить и следующие числа, но последний m.read_byte() уже не нужен будет (ибо числа разделяются одним пробелом), да и надо будет добавить обработку отрицательных чисел (символ '-', у которого код 45). P.s. Не считаю, что это относится к нарушению 8 пункта правил,
  6  Егоров Илья Валерьевич, 23 января 2020 г. 17:27:37
     На CPython — среди решений прошедшие имеются, но оно отчасти сомнительно, поскольку на CPython разница между использованием встроенных функций и велосипеда сильно заметна: велосипед, в силу особенностей интерпретации, медленнее. На PyPy3 с этим гораздо лучше: последнее мое решение использует read_byte из модуля mmap, что потребляет лишь чуть больше килобайта памяти, а по времени спокойно достигает 0.156 сек.
  7  Гильмутдинов Богдан, 23 января 2020 г. 17:14:15
     Эту задачу можно решить на питоне?
  8  Чичигинаров Остап Олегович, 23 января 2020 г. 3:16:37
     что в 16 тесте ваопрвлаорплоаврпаолврпшв
  9  Егоров Илья Валерьевич, 11 января 2020 г. 13:22:25
     Для питонистов: 1) Берите PyPy3, поскольку CPython оптимизирован от слова (почти) никак (особенно в случае requests + gevent, когда на CPython могут быть жуткие проседания, но на PyPy3 вообще никаких проблем — это как пример из реального мира); 2) Для ввода юзайте либо этак word = sys.stdin.buffer.read(n), либо, в лучшем случае, word = os.read(sys.stdin.fileno(), n); 3) int(...) не спасет, word.split(b' ') тем более: парсьте числа вручную; 4) Вопреки законам чистого кода, пишите все в одной функции (обязательно в функции), ибо иначе PyPy3 будет выполнять код в 2 раза дольше, жрать память тоже будет до неразумного много; memoryview (для обертки буфера прочитанных данных) ухудшит ситуацию, но array.array, если вам надо какие-то числа списками хранить (но лучше переменными), может самую малость помочь; 5) Размер буфера выставить этак в 8192, от сортировки откажитесь: обходитесь парой if-elif-else. F) Вполне может выдать 0.187 сек., потребляя около 2 с половиной мегов.
  10  Тургали Махамбет, 14 декабря 2019 г. 17:44:53
     что в 22 тесте?
  11  Ивлев Александр Евгеньевич, 05 ноября 2019 г. 20:27:20
     TL 48 ввод через файлы пробовал, юзаю сканф/принтф, прагмы написал, алгоритм не брутфорс(самое времязанимаемое - это сортировка массива)(пишу на плюсах) ПАМАГИТЕЕЕЕ
  12  Егоров Илья Валерьевич, 20 августа 2019 г. 21:52:43
     Хорошие методы ввода по убыванию производительности: 0) См. пункт 1. В дополнение к там описанному еще и снижение влияния предсказателя ветвлений, зная максимальную длину токена (т.е. вместо проверки достижения конца буфера после каждого символа делаем это после считывания полностью числа). Еще более небезопасно, но еще более быстрее. 1) fread из stdio или in.read из iostream (с отключением блокировки) с кастомным небезопасным парсером. Если верить анализу выхлопа на ассемблере, fread все же быстрее из-за меньшего кол-ва инструкций. Очень быстро, но в прод лучше не надо. 2) fgetc из stdio с тем же парсером, но из-за идентичности логики и отсутствия буферизации смысла не имеет. 3) scanf из stdio. Как компромисс между скоростью, безопасностью и удобством. 4) Ввод через >> из iostream. Медленный, но безопасный и удобный. Отключайте синхронизацию только если уверены, что вы не будете смешивать чтение через stdio и iostream. Вы можете сами убедиться в их производительности, если пожелаете.
  13  Егоров Илья Валерьевич, 20 августа 2019 г. 21:36:53
     Не соглашусь. Без отключения синхронизации iostream будет делать лишние действия, а если вы отключаете синхронизацию для iostream, но используете при этом stdio, то это не имеет смысла. Заметить мало: надо еще и доказать. Увы, мои бенчмарки не подтверждают ваши наблюдения.
  14  Ерёменко Владислав Владиславович, 20 августа 2019 г. 14:49:39
     Давно заметил одну штуку, что обычный файловый ввод-вывод работает лучше таких бустов, как ios_base::sync_with_stdio... и printf, scanf. Поэтому напишите программу через cin, cout и вставьте в самом начале это: ifstream cin("input.txt"); ofstream cout("output.txt"); И всё, тогда пройдёт.
  15  ГРигорий горбаченко, 29 января 2019 г. 18:58:40
     тест который помог 3 -30000 -30000 -30000
  16  Коншин Андрей Сергеевич, 04 сентября 2018 г. 11:14:24
     Если кому-то интересно, почему потоки ввода в C++ медленные, то вот статья: https://habr.com/post/246257/ А если ничего из статья непонятно, то просто перед первым вводов напишите: std::ios::sync_with_stdio(false);
     Ещё рекомендуют std::cin.tie(nullptr);
  17  Винк В В, 27 июня 2018 г. 8:37:44
     Используем <stdio.h> и scanf() и всё заходит за полсекунды. И printf("%lld",ans) нормально работает. Ну и, конечно, алгоритм должен быть близок к оптимальному.
  18  Егоров Илья Валерьевич, 21 апреля 2018 г. 0:31:40
     Кирилл, вот только как это избавит от сохранения всей строки (без использования ctypes)?
  19  Генералов Кирилл Витальевич, 20 апреля 2018 г. 12:05:00
     Илья, у меня появилась идея. Можно сделать подмассив, как срез, из 5 чисел (3 макс. и 2 мин.) и просто двигать его вправо посимвольно, тем самым ища нужные элементы, не взаимодействуя кучу раз со списком. Ну, к примеру, как ползунок на календаре будет работать, только из 5 ячеек.
  20  Егоров Илья Валерьевич, 11 апреля 2018 г. 14:56:05
     По-хорошему, видимо, не следует на Python сохранять всю строку (иначе упирается в память). На уме пока что 3 варианта: 1) Считывать посимвольно (хранить только 1 символ); 2) Считывать частями (своим буфером); 3) Считывать токенами. Представляю лишь реализацию через ctypes, но пока что TLE на 48
 1 2 3

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

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