Всем привет. В данной статье мы рассмотрим полезные вещи, которые можно реализовать на языке C++. Такие знания, как ускорение ввода - вывода могут помочь в решении олимпиадных задач.

Препроцессорные директивы

Для начала разберемся с тем, что такое препроцессор. Препроцессор в языке C/C++ это программа, подготавливающая исходный код вашей программы к компиляции. В данном случае нас больше всего интересует вставка содержимого файла #include, макроподстановки #define и условная компиляция #ifdef, #endif.

#pragma comment(linker, "/STACK:128777216")
/*
 * Строка, увеличивающая размер стека функций
 * На самом деле довольно полезная вещь, при реализации рекурсий
 * !!! Очень частым при больших данных является момент, когда размер изначального стека 
 (в который складываются все данные о функциях) переполняется
 * Такая ситуация вызывает Runtime Error (stack overflow)
*/
#define _USE_MATH_DEFINES
/*
 * В данном случае мы подключаем большую библиотеку математических констант
 * Для вас это ограничится такой константой, как M_PI - числом pi с 
 наибольшой точностью для типа double
*/
#define _CRT_SECURE_NO_WARNINGS
/*
 * Если у вас произойдёт ситуация, в которой вы при работе с Visual Studio столкнётесь с 
 определёнными "небезопасными" функциями из языка C
 * Обычно в этом случае произойдёт ошибка 
 (но только в рамках Visual Studio - в других её попросту нет), 
 связанная с безопасностью
 * Данная же строчка отключит предупреждение и позволит запускать код с данными функциями
 * В основном это связано с scanf, printf, freopen и gets 
 (Visual Studio предложит "безопасные" функции с суффиксом _s)
*/
 
/* !!! Строки выше важно реализовывать перед подключением библиотек 
(т.к. иначе библиотеки начнут работать с дефолтными параметрами) */
#include <iostream>
/*
 * Iostream - хранилище всех функций ввода/вывода, 
 без его подключения для работы с вводом/выводом придётся собирать всё "по кускам"
 * Например, stdio.h - там хранятся scanf/printf, 
 но для удобства iostream подключит их за вас
*/
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
/*
 * Данные библиотеки - набор структур данных, без которых придётся довольно туго
 * string - подключение работы с типом данных строки 
 (бывают ситуации, что Visual Studio компилирует код работы со строками 
 без подключения библиотеки - но будут возникать не предвиденные ошибки)
 * vector - динамический массив, с расширением справа
 * queue - структура "очередь", позволяет работать только с первым элементом, 
 добавление в конец, удаление спереди
 * Библиотека queue также хранит структуру "очередь с приоритетом", она же priority_queue.
 * Очередь с приоритетом позволяет за 
 O(log n) на операцию достать первый элемент и добавить в конец такую операцию, 
 как "поддерживание приоритета" - это значит, что первый элемент будет 
 "самым приоритетным", как пример - наибольшее число
 * stack - структура "стек", позволяет работать только с последним элементом,
 добавляет и удаляет из конца
 * deque - структура "дек", умеет работать, также как и vector, 
 но ещё и имеет возможность эффективно добавлять/удалять спереди
 * set - структура "бинарное дерево поиска", с возможностью добавлять/удалять/находить 
 элемент за O(logn)
 * map - структура "ассоциативный массив", построенный на той же основе, что и set, 
 используя это с ключом
 * Добавляет, удаляет, изменяет и находит элемент (имеется ввиду ключ) за O(logn)
 * unordered_set - структура "хэш-таблица", что в теории позволяет делать добавление, 
 удаление и поиск за O(1)
 * unordered_map - аналогичный ассоциативный массив, построенный на хэш-таблице
 * !!! Несмотря на то, что хэш-таблица звучит привлекательней, это обман - 
 идеальных хэшей не существует
 * !!! Как следствие - скорость работы может падать из-за появления коллизий 
 (хэши двух объектов совпадают, а сами они различны)
 * !!! Кроме того, для решения первой проблемы, 
 таблица умеет перестраиваться, но этот процесс довольно затратный,
 из-за чего делается при превышении определённых пределов
 * !!! Поэтому использование хэш-таблиц может быть не оправданным 
 (например, при большом количестве операций с похожими объектами)
 * !!! Однако лучшее их применение - при работе со строками,
 т.к. сравнение строк - операция, что очень легко может уничтожить время
*/
#include <algorithm>
/* Одним словом - данная библиотека - кладезь различных функций, 
 которые могут вам понадобится
 * Например, операция сортировки
 * Но, на самом деле, много вещей оттуда можно реализовать и самому 
 (что в рамках ограниченного времени будет излишним)
*/
#include <math.h>
#include <cmath>
/* Если вам нужны математические функции и константы - данные библиотеки должны 
 быть под рукой */
#include <climits>
/* Если неожиданно понадобились константы, которые связаны с языком C/C++
 (например INT_MAX), то вам сюда */
#include <ctime>
#include <random>
/*
 * Две специфические библиотеки, 
 которые на практике нужны лишь для стресс-тестирования, однако стоит о них рассказать
 * Первая библиотека - позволяет вытягивать значения времени 
 (например, с её помощью можно вычислить время работы программы)
 * Вторая же полностью посвящена псведослучайным генераторам
 * Самое важное, что может быть оттуда - класс mt19937 - генератор псевдослучайных чисел, 
 который позволяет генерировать любые случайные числа 
 (rand же на самом деле работает только в рамках константы RAND_MAX,
 что не превышает тип short, чего бывает мало)
 * Причём этот генератор ещё и качественный - он проходит тесты diehard, 
 которые являются одними из трудных */
#ifdef _DEBUG
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
#endif
 /*
 * Поговорим о блоке кода, что был описан через конструкцию ifdef
 * Для начала объясню структуру ifdef. Как было замечено ранее,
 #define задаёт некоторые строки
 * Если воспользоваться например Visual Studio, то они начнут
 окрашиваться в определённый цвет
 * На самом деле конструкция #define позволяет устанавливать своего 
 рода флаги, а также "сжимать" некоторый код посредством заданных конструкций
 * Например, если у вас всегда будет for (int i = 0; i < n; ++i), 
  то можно в глобальной области перед main определить следующую строку
 * #define forx(i, n) for(int i = 0; i < n; ++i)
 * Чем это замечательно? Теперь можно использовать forx(i, n), 
 что может сэкономить при написании на скорость
 * Так вот, конструкция #ifdef позволяет проверять, 
 установлен ли при помощи #define такой то флаг
 * Т.е. это просто условный оператор, только работающий на уровне прекомпиляции
 * Код, который будет получен после компиляции - не будет содержать данных конструкций - 
 во-первых все "сжатия" заменятся на то, что сжималось, во-вторых все конструкции 
 #ifdef заменятся на тот блок кода, который в этом случае должен работать
 * Например, если _DEBUG был определён, то программа попытается работать с файлами
 * А если нет, то у нас там останется ничего
 * И при этом по скорости работы мы ничего не потеряем (а даже преуспеем, в
 едь условный оператор на самом деле втихаря имеет свою нагрузку)
*/

Быстрый ввод - вывод

 ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    /*
     * Данная строка - основное ускорение ввода/вывода в C++
     * sync_with_stdio - отключает синхронизацию различных потоков, 
     вследствие чего смешивание cin & scanf, cout & prinf приведёт к 
     неправильным результатам, зато в рамках cin/cout получаем заметный прирост
     * cin/cout.tie - отключает сброс буфферных потоков при переключении - 
     что опять-такие даёт прирост
     * !!! Несмотря на полученный прирост, данные строки всё-таки отключат
     "безопасный режим", 
     который нужен в промышленном программировании, 
     поэтому их использование лучше оставить только в рамках решения олимпиадных задач
    */
/*
 * Следующие две функции - гордость оптимизаций ввода/вывода
 * Чем они хороши? Позволяют довольно быстро вводить/выводить числа
 * В чём минус? Во-первых требуется разбираться в такой конструкции - 
 довольно легко сделать опечатку и получить TLE/WA
 * Кроме того, для разных данных - разные функции.
 * !!! Однако при малых данных ввода/вывода прирост не будет замечен, 
 но при количестве данных > 10^4 всё сильнее и сильнее будет виден
 * Например, то, что сделает cin/cout за ~1 секнуду, 
 данные функции позволяют делать это же самое за жалкие 0.05 секунды
*/
inline int FastIn(FILE* streamin = stdin) {
    char c = ' ';
    bool mns = false;
    int a = 0;
    while (!isdigit(c)) {
        mns = c == '-';
        c = _getc_nolock(streamin);
    }
    while (isdigit(c)) {
        a *= 10;
        a += c - '0';
        c = _getc_nolock(streamin);
    }
    return (mns ? -a : a);
}
 
inline void FastOut(int val, FILE* streamout = stdout) {
    if (val < 0) {
        val = -val;
        _putc_nolock('-', streamout);
    }
    bool fst = true;
    const int degree = 1000000000;
    for (int i = degree; i > 0; i /= 10) {
        int dl = val / i;
        if (dl || !fst) {
            _putc_nolock('0' + dl, streamout);
            fst = false;
        }
        val %= i;
    }
    if (fst)
        _putc_nolock('0', streamout);
    _putc_nolock('\n', streamout);
}

Рандом и плавающая запятая

cout.precision(20); cout.setf(ios::fixed);
    /*
     * Первое - позволяет выводить числа с плавающей точкой вплоть до X 
     (в данном случае - 20) цифр после запятой
     * Второе - фиксирует, чтобы всегда выводилось именно X цифр после запятой
     * Данные строки влияют только на типы данных float, double и long double -
     других не касается никак
    */
 mt19937 rndm;
    rndm.seed(time(0));
    /*
     * Как я говорил, mt19937 - высококачественный генератор псевдослучайных чисел.
     * Этими двумя строками мы можем его проинициализировать 
     (задать название, а также установить зерно)
     * Для того, чтобы ваши числа от запуска к запуску оставались случайными, 
     зерно следует задавать через данные о времени
     * Сам же этот рандом вызывает числа как и обычный - rndm()
    */