Блог пользователя nongi

Автор nongi, история, 6 лет назад, По-русски

Доброго времени суток, товарищи олимпиадники!
Некоторое время назад взялся за решение не сложной старой задачи из архива codeforces 222B - Cosmic Tables. В ней необходимо вводить и выводить большое количество данных, в связи с чем было решено использовать scanf и printf. Мне стало интересно, как ещё я мог бы ускорить своё решение. Я начал экспериментировать со всем, что пришло в голову, в частности — компилятор. Код, который получился в итоге, был написан, по сути, на языке С. На С++ 17 стандарта он заходил меньше чем за секунду 47853314, но на С этот же код падал по времени на 54 тесте 47853345. Скорее всего ошибка таится на поверхности, но мне никак не удается найти на неё ответ. Может ли кто-то помочь мне с этим? P.s. что обычно делаете вы для ускорения ваших реализаций? P.s.s. возможно есть место, предназначенное для подобных вопросов... Был бы рад, если кто-нибудь подсказал мне его.

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Буду рад любой вашей догадке!

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Попробовал отправлять с флашем потока вывода после каждого printf. Так же попробовал переделать массив в одномерный. Ничего не помогает понять, как именно плюсовый компилятор преобразует код, чтобы он работал меньше секунды... Побит, но не сломлен!

»
6 лет назад, # |
Rev. 9   Проголосовать: нравится +2 Проголосовать: не нравится

Ввод/вывод без буферизации в программах очень медленные. Существуют разные техники буферизации с точки зрения эффективности и побочных эффектов, и техники, используемые в C и C++ по умолчанию, не очень быстрые, что является достаточно известной проблемой, впрочем, не особо актуальной для современного codeforces, так как современные задачи делаются с расчётом на то, чтобы скорость ввода/вывода не играла особой роли.

Пишем собственную буферизацию и получаем 186ms на чистом C (реализацию скомуниздил у Burunduk1)

Я не спец в чистом C, видимо там встроенная буферизация совсем отстойная.