Быстрый ввод-вывод в C++
Часто бывает так, что ввод и/или вывод в задаче очень большие. В этом случае только считывание входных данных и вывод ответа уже могут не уложиться в ограничение по времени. Чтобы этого избежать, есть различные техники, которые мы рассмотрим в этой главе.
endl и \n
Обычно перевод строки делается при помощи cout << endl, однако эта команда не только переводит строку, но и очищает буфер. Когда вы что-то выводите, на самом деле оно не обязано выводиться сразу. Программа сначала накопит какой-то буфер вывода, а потом выведет его целиком, потому что сама по себе операция вывода весьма долго работает. Однако если вы пишете endl, то вы заставляете программу насильно очистить буфер. Если вы будете делать это очень часто, то программа будет работать очень долго. Чтобы решить эту проблему, можно вместо endl использовать cout << '\n'. Отличие заключается как раз в том, что это просто символ перевода строки без очистки буфера. В случае, если вы в выводе часто делаете перевод строки, это может существенно ускорить вашу программу.
Однако не стоит везде всегда писать \n вместо endl. В интерактивных задачах важно, чтобы после каждого вывода очищался буфер, чтобы программа, с которой вы взаимодействовала, могла сразу считать то, что вы вывели. Поэтому в интерактивных задачах обязательно использовать endl для очистки буфера.
Кроме того, если вы пытаетесь найти ошибку в программе и выводите отладочную информацию, вам важно, чтобы она появлялась на экране, поэтому ее тоже нужно выводить с очисткой буфера. Если вы не хотите при этом переводить строку, можете воспользоваться std::flush.
sync_with_stdio и cin.tie
Также сильно ускорить программу можно, отключив синхронизацию разных потоков ввода/вывода. Можно использовать следующие две строчки:
ios::sync_with_stdio(0);
cin.tie(0);
Первая строка отключает синхронизацию iostream и stdio, то есть вы не можете больше одновременно использовать и cin, и scanf в одной программе. Однако вряд ли вам это нужно, поэтому эту синхронизацию можно отключить, что приводит к ускорению программы.
Вторая строка отключает привязку cin к cout, что помогает в случае, когда ввод и вывод чередуются. Кроме того, некоторые люди иногда используют cout.tie(0), но эта строка не делает ничего, потому что пытается отключить привязку cout к cout, что весьма странно. Миф о том, что cout.tie полезен подкрепляется примерами, когда при добавлении этой строки код ускорялся, однако при повторных запусках могла наблюдаться обратная ситуация. Разное время работы связано с разными условиями запуска и фазами Венеры, но не с добавлением этой строчки.
Ручной быстрый ввод-вывод
Если даже предыдущие оптимизации не помогают, можно воспользоваться рукописным быстрым вводом. Это будет еще в несколько раз быстрее. К примеру, можно воспользоваться вот этим кодом от Сергея Копелиовича. Пример использования:
int n = readInt();
writeInt(n, ' ');