Здесь находится информация о том, как сдать курс АиСД и выжить

Ссылки

ПУД
Канал курса в telegram для объявлений. Здесь будут публиковаться объявления по курсу, выложенные домашки, дедлайны и т.д.
Чат курса в telegram. Здесь можно задать вопросы по задачам, узнать что-то по теме (и не только) и т.д.
Styleguide — обязателен к прочтению и соблюдению.
Как сдавать домашние задания
Как настроить окружение на своем компьютере
Что делать, если решение не проходит в контесте

FAQ

Как получить доступ к Яндекс.Контесту? Напиши в чат курса, и тебе выдадут доступ.
Как оцениваются решения в Яндекс.Контесте? Читай методичку.
Почему на компьютере решение работает, а в контесте падает? Читай методичку.
Считается ли списывание из открытых источников списыванием? Да, считается. Любой копипаст кода считается списыванием. Когда Вы списываете из открытых источников, имейте в виду, что Вы не один такой хитрый на этом курсе. И мы вас найдём и будем подозревать, что вы списали друг у друга. Обязательно указывайте источники, которыми пользовались при решении ДЗ.
У меня в задаче стоит OK (до оффлайн-проверки) — значит ли это, что у меня за неё уже минимум 8 баллов? Нет, не значит. При выявлении списывания или же читерства (к примеру, в контесте / задаче явным образом запрещалось использовать std::sort или что-то аналогичное, а Вы взяли и заюзали каким-то хитрым образом) она зануляется.
...
...

Стайлгайд

Прежде, чем писать какой-либо код, обязательно прочитайте C++ Style Guide, на нашем курсе мы требуем полного выполнения Google C++ Style Guide с небольшими изменениями (касающимися нейминга и прочего; смотрите далее)

Какие пункты из Google C++ Style Guide наиболее важны:

Scoping
- Local Variables
- Static and Global Variables
Classes
Functions
- Parameter Ordering
- Write Short Functions
- Reference Arguments (с оговоркой про выходные параметры примитивных типов в п. 17)
Other C++ Features
Naming
Formatting

Ваша задача на этом курсе — написать наиболее простой, понятный, эффективный, читаемый и гибкий код среди тех, которые проходят ограничения по времени и по памяти. То есть в первую очередь должна быть правильной асимптотическая сложность, а потом сразу же думайте, как все сделать максимально просто.

Боритесь с дублированием кода.

Это самое большое возможное зло. Если в процессе написания вам понадобилось копировать и вставить кусок своего кода в этот же код, то это первый признак того, что происходит дублирование. Постарайтесь детектировать идентичные и похожие места, вынесите общую часть в отдельную функцию или класс и воспользуйтесь ей дважды с разными аргументами.

Старайтесь писать аккуратно.

Удаляйте лишний, неиспользуемый, закомментированный код, удаляйте переменные и функции, которые вам на самом деле не нужны, остальные называйте понятно.

Синтаксис

На код должно быть приятно смотреть, его должно быть легко читать. Вы его пишете один раз, сохраняете, после чего его читают много раз, поэтому выгодно потратить при написании немного времени на приведение кода в порядок, чтобы впоследствии сократить своё и чужое время на чтение. Простые правила ниже служат для улучшения визуального восприятия.

Используйте 4 пробела для отступа. Данный размер отступа является наиболее распространенным, поэтому используйте его всюду для единообразия. 3-4 пробела также являются оптимальными размерами для отступа согласно NASA.
Вокруг всех бинарных операторов (=, ==, +, -, *, /, >, << и др.) должны быть пробелы с обеих сторон. Исключением являются операторы ., ->, ::.
После запятой должен быть пробел.
Между закрывающейся круглой скобкой и открывающейся фигурной должен быть пробел.
Не жадничайте с пустыми строками. Вставляйте всегда пустые строки между определениями глобальных функций, классов, констант, typedef'ов, include'ов, между объявлениями методов и функций, между реализациями функций, между объявлениями классов и реализациями функций и т.д.
Вставляйте пустые строки в код реализации функций, чтобы подчеркнуть разделение логических частей кода.
Не размещайте if, else, for, while и др. на одной строке со своим statement:
```
if (condition) statement;
else statement;
...
for (...) statement;
```
Это, во-первых, ухудшает читаемость кода. Вы можете вообще один из statement'ов не заметить или ошибочно решить, что он относится к if'у:
```
if (number % 2 == 0) std::cout << "Even\n"; even = true;
```
А во-вторых, при отладке debugger'ом невозможно понять, выполнив команду «Step Over», выполнилось или не выполнилось условие (или сколько итераций цикла прошло).
Также рекомендуется всегда обрамлять if, else, for, while фигурными скобками:
```
for (size_t index = 0; index < array.size(); ++index) {
    statement1;
    statement2;
    ...
}
```
```
for (auto number : array) {
    statement1;
    statement2;
    ...
}
```
даже если внутри только один statement.
```
if (number % 2 == 0) {
    std::cout << "Even\n";
}
```
Это более читаемо и безопасно. В варианте без скобок легко ошибиться, например, вот так:
```
if (number % 2 == 0)
    std::cout << "Even\n";
    even = true;
```
Легко подумать, что код even = true; тоже находится под if'ом.

Язык C++

Существуют разные языки программирования: C, C++, Java, Python и великое множество других. Между ними есть очевидные внешние сходства и различия: как написать цикл, как определить оператор, как создать класс. Однако основные их отличия кроются в принятых в них методах решения типовых задач и инструментах: если писать цикл по индексу, то какие должны быть его границы? если определить оператор, каков должен быть тип принимаемых аргументов и возвращаемого значения? если создавать класс, какие переменные-члены стоит в нем определять, какие методы, что следует вынести во внешние функции? На все эти вопросы можно дать разные ответы, и все они будут отчасти верными. Есть и общие рекомендации и конструкции, которые зарекомендовали себя за долгое время использования, как надежные и удобные, а также примеры, как делать не надо. Некоторые из них описаны в этом разделе.

#include <bits/stdc++.h> использовать нельзя.
Подробнее
1. Увеличивается время компиляции при подключении данного заголовочного файла. В случае стандартной библиотеки разницу во времени компиляции вы не увидите, но когда у вас будет большой проект, то это будет уже существенно влиять на время компиляции (чтобы она шла 3 минуты, а не 30).
2. Некоторые компиляторы не поддерживают данный заголовочный файл (такие, как MSVC, XCode и другие).
Подключайте только те библиотеки, которые вы используете.
Не подключайте C-шные библиотеки с помощью #include <название_библиотеки.h>.
Пример

Пишите не так:
```
#include <math.h>
```
А так:
```
#include <cmath>
```
using namespace std; использовать нельзя.

Подробнее

Включать целый namespace опасно, так как из-за этого может возникнуть конфликт имен. Вследствие чего могут возникнуть нетривиальные ошибки компиляции/линковки, а если не повезет, то переменная из namespace может совпасть по названию с какой-то вашей переменной, про которую вы не помните ее область видимости, что приведет к еще более сложнонаходимым багам, хоть все и скомпилируется, но иногда вы будете использовать переменную, думая, что это ваша переменная, и в ней такое-то значение, а значение будет совсем другим. Если нужно использовать много раз std::vector, напишите using std::vector; если cout, то using std::cout; и т.д. Кроме того, включая namespace, вы нарушаете сам принцип использования namespace'ов.
Использовать массивы фиксированной длины int[], int* не рекомендуется — используйте вместо них std::vector<int>. Использование конкретных структур данных обуславливается темой контеста и требованиями к задаче.
Не используйте C-type строки char[] и char* - используйте вместо них std::string.
Не используйте ввод-вывод в стиле С через функции scanf, printf.

Подробнее

Используйте вместо них операторы >> и << у std::cin и std::cout соответственно. Если при этом в задаче большой размер ввода-вывода (от 100000 чисел), то необходимо использовать несколько дополнительных приемов, чтобы ваш ввод-вывод работал достаточно быстро, иначе вы можете получить Time Limit Exceeded. Эти приемы описаны ниже.
Пример на пункты 4 — 7:
```
#include <algorithm>
#include <string>
#include <vector>

using std::string;
using std::vector;

vector<string> input() {
    size_t rows;
    std::cin >> rows;
    vector<string> table;
    table.reserve(rows);
    for (size_t row = 0; row < rows; ++row) {
        string line;
        std::cin >> line;
        table.push_back(line);
    }
    return table;
}

vector<string> process(vector<string> table) {
    std::reverse(table.begin(), table.end());
    return table;
}

void output(const vector<string>& table) {
    for (const auto& row : table) {
        std::cout << row << std::endl;
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    const auto& table = input();
    table = process(table);
    output(table);
    return 0;
}
```
Важно: По умолчанию для iostream включен режим совместимости с stdio, который позволяет одновременно использовать оба интерфейса для ввода/вывода. В этом режиме производительность std::cin и std::cout понижается в несколько раз.
Подробнее

Поэтому если размер ввода/вывода имеет порядок от 100000 чисел, вам надо будет отключить этот режим. Делать это надо до совершения каких-либо операций ввода-вывода, желательно первой же строкой в программе:
```
#include <iostream>

int main() {
    std::ios_base::sync_with_stdio(false);
    ...
    return 0;
}
```
Также обратите внимание на то, что std::cout может работать слишком медленно, если вы выводите порядка 100000 чисел или более, и при этом у std::cout регулярно очищается буфер. Буфер очищается при каждом выводе std::endl, так что в случае большого вывода лучше выводить "\n" вместо std::endl. Также буфер std::cout очищается при каждом вводе через std::cin — это связано с тем, что при пользовательском вводе-выводе через обычный std::cin и std::cout в консоли необходимо перед тем, как запрашивать очередной ввод от пользователя, показать ему последний вывод перед этим, а значит и очистить буфер. Эта проблема для задач с большим выводом решается с помощью вызова std::cin.tie(nullptr); в самом начале программы. Выполнение всех этих рекомендаций приведет к тому, что ввод-вывод при помощи потоков std::cin и std::cout будет работать не медленнее ввода-вывода через printf и scanf на задачах с большим вводом-выводом. Подробнее см. здесь.
Если используется значение типа истина/ложь, то используйте тип bool, а не int.
Не используйте тип long.

Подробнее

Более стандартный тип — int, к нему у всех уже привыкли глаза, и long с теми же намерениями — просто смотрится странно. На 32-битных машинах оба типа являются 32-битными и ничем не отличаются, поэтому используйте int вместо long. Если вам нужен 64-битный тип, придется воспользоваться типом int64_t.
При прочих равных, используйте преинкремент ++i, а не постинкремент i++. Это полезная привычка. В случае int'ов это все равно, но если у вас будет в коде сложный итератор, то в процессе постинкремента создается его копия в памяти, что может создать вам неожиданные тормоза и повышенное использование памяти, а догадаться о том, что вся проблема — в коротком выражении it++ — будет сложно.
main должен заканчиваться return 0;, в противном случае на некоторых компиляторах программа может завершиться с ненулевым кодом возврата, что в свою очередь приводит к Runtime error в тестирующей системе.
Вставляйте слово const везде, где только это возможно по смыслу.

Подробнее

Если какая-то переменная по сути меняться в функции не должна, она должна быть const. Если метод класса не меняет при вызове содержимое класса, он должен быть const-методом. Таким образом вы обезопасите себя от многих глупых ошибок: они отловятся еще на этапе компиляции.

Если у вас из-за того, что вы где-то поставили в правильном месте const, не компилируется код, то const выполнил свою главную задачу. Тогда надо не его убирать, а найти и исправить проблему в другом месте: вы где-то еще забыли поставить const или изменяете переменную, которую не собирались изменять. Надо в этом разобраться, доставить const туда, где он еще нужен, а не удалять там, где он вам «мешает».
Используйте везде в программе индексацию с нуля.

Подробнее

Если какие-то входные или выходные данные в задаче используют индексацию с единицы, лучше в функции ввода, соответственно вывода, переведите индексацию из одной системы в другую, а везде внутри программы, помимо функций ввода и вывода пользуйтесь индексацией с нуля. Весь язык C++ так спроектирован, что индексация с нуля гораздо удобнее, а как только вы начинаете использовать индексацию с единицы, становится неудобно, появляются вычитания единицы из переменных по всему коду и т.д.
Задумывайтесь о переполнениях типов. Если у вас есть две переменные типа int, значение каждой равно миллиону, и вы их перемножаете, то тип переполнится (максимальное значение — \(2^{31} - 1\)), и вы получите неправильный результат. Необходимо перед перемножением привести обе переменные к 64-битному типу int64_t. Если у вас есть две int переменные со значением два миллиарда и вы их складываете, — тоже произойдет переполнение, тоже нужно предварительно приводить к int64_t.
Не вычитайте никогда просто так ничего из container.size(), где container — какой-нибудь контейнер из STL.
Подробнее

Например, vector.size() возвращает беззнаковый size_t (который обычно просто синоним для unsigned long), и если вы будете из него вычитать, то можете легко получить переполнение. Например, если вектор пустой, а вы вычитаете единицу, чтобы узнать последний элемент, или вектор состоит только из одного элемента, а вы вычитаете 2, чтобы узнать предпоследний элемент, и т.д. Всегда приводите результат вызова size() к int'у, если вам совершенно необходимо вычесть из size(), либо постарайтесь переписать сравнение без операции вычитания. При этом в самом распространенном случае, когда вам нужно написать цикл for, проходящий по всем элементам, кроме, скажем, последних десяти, надо просто писать не так
```
// Wrong! If container.size() < 10, you'll get an infinite cycle.
// This code won't compile with the -Werror flag.
for (int index = 0; index < container.size() - 10; ++index) {
    ...
}
```
В этом цикле, если, к примеру, container.size() == 5, то вы получаете реально цикл
```
// Note that 4294967291 > MAX_INT, so the cycle is infinite
for (int index = 0; index < 4294967291; ++index) {
    ...
}
```
А пишите лучше всегда так
```
// Correct: size_t and adding instead of subtracting
for (size_t index = 0; index + 10 < container.size(); ++index) {
    ...
}
```
ну или хотя бы так
```
// Correct: casted to int
for (int index = 0; index < static_cast<int>(container.size()) - 10; ++index) {
    ...
}
```
Соответственно, если вам нужно вызвать функцию, в которую вы должны передать индекс первого и последнего элемента вектора, то делайте это так:
```
someFunction(0, static_cast<int>(container.size()) - 1)
```
По-хорошему, здесь надо бы еще проверять, что в контейнере что-то есть, но к int'у приводить надо в любом случае, иначе появляются неочевидные баги.
Не пользуйтесь макросами для определения констант.
Подробнее

Макросы — это очень опасная и неудобная вещь. Их раскрывает специальный препроцессор, который начинает работать еще до компилятора C++, и он ничего не знает о самом языке. Все конструкции раскрываются буквально. В связи с этим есть множество возможных неочевидных побочных эффектов, а у компилятора нет возможности выполнить проверку типов, константность и т.д. Читайте более подробно об этом в книге Майерса «Effective C++».

Итак, неправильный вариант:
```
#define MAX_LENGTH 100000  // Wrong! Don't use macros!
```
Правильный вариант:
```
constexpr int kMaxLength = 100'000;  // Correct
```
Входные параметры передавайте в функцию по константной ссылке; по ссылке — чтобы они лишний раз не копировались, по константной — чтобы вы не могли их случайно изменить. Не забывайте про const! Выходные параметры передавайте в функции по указателю — чтобы вы могли их изменить; по указателю, а не по ссылке, — чтобы вы могли в месте вызова отличить входные параметры от выходных по амперсанду перед именем переменной. Размещайте входные параметры перед выходными в списке параметров функции или метода. Аргументы примитивных типов следует передавать в функции по-другому. Входные параметры типов int, char, bool, double передавайте по значению. Они будут копироваться, но это так же почти бесплатно, как и в случае ссылок или указателей. При этом вы не сможете их изменить изнутри функции, что и нужно, т.к. это входные параметры. Если вам нужны эти типы как выходные параметры функции, лучше передавайте их по ссылке, т.к. иначе легко внутри функции перепутать указатель на переменную с самой переменной, и сделать совсем не то, что вы собирались.
Примеры:
```
void input(std::vector<Point>* sequence, int& points_to_cover);

void findMaximumsInSlidingWindow(
    const std::vector<int>& sequence, 
    const std::string& shifts, 
    vector<int>* maximums);

double findMinimumCoveringCircleRadius(
    const std::vector<Point>& points, 
    int points_to_cover);
```
Примеры вызовов:
```
std::vector<int> sequence;
int points_to_cover;
input(&sequence, points_to_cover);
...
...
std::vector<int> sequence;
std::string shifts;
input(&sequence, &shifts);
std::vector<int> maximums;
findMaximumsInSlidingWindow(sequence, shifts, &maximums);
...
...
double min_radius = findMinimumCoveringRadius(points, points_to_cover);
```
Обратите внимание на амперсанды & перед переменными, в которые записывается результат вызова функции. Если функция возвращает одну величину, пусть она делает это по значению. Это столь же быстро, зато удобнее в месте вызова. Пример:
```
std::vector<int> readNumbers(std::istream& input_stream = std::cin) {
    size_t sequence_length;
    input_stream >> sequence_length;
    std::vector<int> numbers(sequence_length);
    for (size_t i = 0; i < numbers.size(); ++i) {
        input_stream >> numbers[i];
    }
    return numbers;
}

int main() {
    std::vector<int> first_sequence = readNumbers();
    std::vector<int> second_sequence = readNumbers();
    ...
}
```
Лишнего копирования в этом месте не возникнет. Дело в том, что эта операция настолько часто встречается, что компиляторы научились ее распознавать и генерировать эффективный код для нее. Технология называется return value optimization, известна также под своей аббревиатурой RVO. Можно и следует по умолчанию считать, что она есть и исправно работает, и писать код так, чтобы им было удобнее пользоваться. Чтобы узнать об этом более подробно, поищите в вашем любимом поисковике ее описание по названию. Если переданный на вход параметр для выполнения алгоритма необходимо изменять, — это не означает, что параметр автоматически становится выходным параметром. Если целью алгоритма не является менять входной параметр, то изменять этот параметр функция не должна: пользователь алгоритма этого не ожидает, и будет очень не рад такому побочному эффекту. Кроме того, если просто передать параметр по ссылке и поменять его внутри, то пользователь даже не будет догадываться о том, что переданные им данные будут изменены. Появляющиеся вследствие таких побочных эффектов баги очень тяжело искать. Соответственно, в таких ситуациях есть два решения: передавать параметр по значению или передавать как обычно по константной ссылке, а внутри функции копировать и изменять уже копию. Первый вариант (передавать по значению) обычно предпочтителен. Т.к. объект передается по значению, его можно менять внутри функции в процессе работы алгоритма (например, сортировать, если это вектор), при этом объект не изменится в месте вызова функции. При копировании аргумента, переданного по константной ссылке, в функции появляется два одинаковых по смыслу объекта, что может привести к путанице и использованию одного из них вместо другого, кроме того, копировать приходится вручную, тогда как при передаче объекта по значению копия делается автоматически, без написания дополнительного кода. Пример:
```
std::vector<int> unique(std::vector<int> numbers) {
    // here we sort a copy of given numbers,
    // so that the user does not lose his data
    std::sort(numbers.begin(), numbers.end());
    numbers.erase(
        std::unique(numbers.begin(), numbers.end()),
        numbers.end());
    return numbers;
}
```
Разделяйте использование class и struct: классом должна быть любая сущность, которая содержит в себе логику, тогда как структура — это набор данных, объединенных в один объект. В классе все переменные-члены должны быть приватными, для доступа к ним делайте аксессоры, в структуре все переменные должны быть публичными, нетривиальных методов быть не должно.
Пример
```
struct Point {
    double x, y;
};

// Compares first by x-coordinate, then by y-coordinate
bool operator<(const Point& first, const Point& second) {
    if (first.x != second.x) {
        return first.x < second.x;
    }
    return first.y < second.y;
}

class Path {
public:
    Path(double time, double average_speed)
        : time_(time), average_speed_(average_speed)
    {}
    
    double time() const {
        return time_;
    }
    
    double averageSpeed() const {
        return average_speed_;
    }
    
    double distance() const {
        return time_ * average_speed_;
    }

private:
    double time_;
    double average_speed_;
};
```
От структуры точки нам ничего не требуется, поэтому она состоит только из двух публичных полей. Метод compare добавлять нельзя, задача сравнения решается определением внешнего оператора <. Если нужно, например, запретить изменять координаты (устанавливать их только при создании точки), то ее нужно делать классом с двумя get-аксессорами. В классе Path хранятся две величины, а получать требуется три. Если бы time и average_speed были публичными переменными, то доступ к значениям скорости и времени происходил бы как path.time и path.average_speed, а доступ к пройденному расстоянию — как path.distance(). Для нахождения расстояния приходится добавлять скобки, то есть всегда приходится помнить о том, что расстояние — это метод, а время и скорость — переменные. Если по какой-то причине (например, недостаточная точность) в будущем хранимые переменные нужно будет поменять и перейти к системе (время, расстояние), то в нашем случае с приватными переменными лишь изменится реализация методов, сохранив интерфейс класса. В случае же с публичными переменными придется изменять интерфейс класса, что немедленно влечет изменение всего кода, который его использует. Хранить все три величины переменными категорически нельзя: если время было равно 1, то действие path.time = 0.0 нарушит инвариант time * speed == distance, что приведет к совершенно непредсказуемым последствиям. Итак, если вам нужно хранить данные под общим именем, вам подойдет структура; во всех остальных случаях создавайте полноценный класс только с приватными переменными-членами.
Старайтесь не использовать по возможности динамическое выделение памяти (с помощью new и malloc):
Почему
если вы будете его использовать, вам необходимо будет заботиться и об «уборке мусора», т.е. освобождении памяти. Правильный, безопасный способ это делать — не очень простой и не входит в материалы курса. Кроме того, вызов new довольно медленный, поэтому если очень много раз это сделать, то можете не влезть в Time limit. Если вам интересно, как правильно управлять динамической памятью, читайте книгу Майерса «Effective C++» или наберите в поисковике «RAII».
При использовании vector имейте в виду, что у него есть удобные методы: различные конструкторы, позволяющие задать размер и значение элемента вектора по умолчанию, операторы присваивания, сравнения (лексикографического) и оператор swap.
Примеры:

Создание двумерного вектора размером rows * columns, заполненного значением 100:
```
std::vector<std::vector<int>> cache(
    rows,
    std::vector<int>(columns, 100));
```
Перестановка двух векторов местами без копирования всего содержимого:
```
std::vector<int> first(1000000, 1);
std::vector<int> second(2000000, 2);
first.swap(second);
```
Здесь меняются местами реально два внутренних указателя int*, что значительно эффективнее, чем копирование векторов целиком, особенно если они большого размера.
Обратите внимание, что для взятия модуля вещественного числа (float, double) необходимо пользоваться функцией fabs, а не abs. При этом в Microsoft Visual Studio сделана перегрузка abs, которая работает и для вещественных чисел даже если вы не подключили заголовочный файл с ней напрямую. Однако на сервере при этом будет abs(-2.75) != 2.75.

В общем же случае стоит отметить, что в C++ существует 2 версии abs:
- в cmath, определенная для вещественных чисел (float, double и long double).
- в cstdlib, определенная для целых чисел (int, long и long long).
Распространенная ошибка состоит в том, что подключается cmath и используется abs оттуда, что приводит к приведению целых типов в double, что в свою очередь может приводить к ошибкам округления при вызове abs(long long).

Поэтому общее правило следующее:
- для взятия модуля вещественного числа необходимо подключить cmath и использовать fabs.
- для взятия модуля целого числа необходимо подключить cstdlib и использовать abs.
Если вы пользуетесь стандартом c++11(c++0x), то для генерации (псевдо)случайных чисел рекомендуется использовать заголовок random с генератором псевдослучайных чисел std::mt19937 и распределениями:
```
std::uniform_int_distribution
std::uniform_real_distribution
```
и другими, если понадобятся.
Подробнее

В противном случае, имейте в виду, что значение RAND_MAX — ограничение сверху на значения, выдаваемые функцией rand(),— отличается в разных компиляторах. Тщательно изучите, какое значение данной границы в вашем компиляторе, а какое — в компиляторе в автоматической системе (компилятор вы выбираете при сдаче задания). Подходит ли вам такое ограничение сверху, или нужно построить на базе функции rand() алгоритм, позволяющий возвращать случайные числа, равномерно распределенные в более широком диапазоне, чем [0, RAND_MAX - 1]? При использовании схемы, предложенной стандартом c++11|(c++0x), следует обратить внимание на то, где создавать генератор. Каждый алгоритм должен использовать собственный генератор, чтобы добиться независимой работы всех алгоритмов. Например, два алгоритма, использующих случайность, должны работать одинаково, вне зависимости от порядка их вызовов. Такой независимости сложно добиться при использовании функции rand(). Например, если вы хотите реализовать рандомизированный алгоритм сортировки, то нужно создать генератор внутри внешней функции, которую и будет вызывать пользователь, и передать его во внутреннюю, где будет реализована вся логика сортировки:
```
#include <random>

template <class Iterator>
void sort(Iterator begin, Iterator end) {
    std::mt19937 generator;
    quickSort(begin, end, generator);
}
template <class Iterator, class RandomGenerator>
void quickSort(Iterator begin, Iterator end, RandomGenerator& generator) {
    ...
}
```
В большинстве случаев нельзя сравнивать числа типа float и double просто операторами <, >, <=, >=, ==:
Почему

При вычислениях в вещественных типах накапливается погрешность, вследствие чего равные по сути числа, вычисленные с помощью разной последовательности действий, могут получить различные значения в типах float и double, и даже a < b может измениться на b < a. Погрешность вычислений можно оценить, используя точные знания о том, как именно выполняются арифметические операции, а также как происходят вычисления в используемых вами функциях. Обычно делать этого точно не нужно, т.к. точность типа double позволяет хранить 15-16 знаков, а требуемая в задаче точность обычно порядка \(10^{-6}\) или \(10^{-9}\), но не меньше. Однако для того, чтобы корректно сравнивать числа, следует использовать порог сравнения. Примеры:
```
const double kComparisonThreshold = 1e-8;

bool less(double first, double second) {
    return first < second - kComparisonThreshold;
}

bool lessOrEqual(double first, double second) {
    return first < second + kComparisonThreshold;
}

bool equal(double first, double second) {
    return fabs(first - second) < kComparisonThreshold;
}
```
Для своих типов (классов, структур), если объекты типа необходимо сравнивать между собой, реализуйте всегда operator< и не реализуйте остальные операторы сравнения (operator<=, operator>, operator>=):
Почему

Через operator< выражаются все остальные, и общепринятая конвенция — реализовывать только сравнение на «меньше». В противном случае, дублируется код, а работа различных операторов может оказаться несогласованной. Точно так же, общая конвенция, — что сортировка объектов по умолчанию делается по возрастанию, и в качестве компаратора передается функция сравнения на «меньше». Это правило необходимо соблюдать, чтобы вашу программу было легко понимать другим программистам.
Не используйте std::pair (за исключением случая, описанного ниже).

Подробнее

Причина в том, что в месте использования объекта pair невозможно понять, что кроется за полем first, а что — за полем second. Это абстрактные названия, которые могут означать что угодно, а в месте использования никаких указаний на это нет. Даже если в месте определения переменной указать, что в ней хранится в first и second, при чтении придется постоянно возвращаться к месту определения переменной, чтобы разобраться в коде и убедиться, в частности, что first и second нигде не перепутаны местами — часто встречающаяся ошибка! Исключением являются небольшие участки кода (помещающиеся на один экран), в рамках которых создается из имеющихся объектов pair, далее удобно используется для какой-нибудь операции (например, сортировка), и затем все pair обратно «расшифровываются» в новые объекты и более не используются. Это может быть удобно для сортировки по вторичному параметру, т.к. для pair есть оператор сравнения по умолчанию, который сравнивает сначала по first, затем по second. При этом код легко понять, т.к. pair определен и используется в одном очень локальном куске кода, который можно охватить взглядом целиком.

Организация кода

Как и любая система, код при разрастании становится все более путаным и сложным. Однако есть способы перевести эту сложность преимущественно в его размер, сохраняя логику ясной и прозрачной. Помогает в этом грамотное структурирование: что может быть классом, что должна делать функция, где что должно объявляться. Оно же позволяет удобно осуществить повторное использование нужных участков кода.

У каждой переменной должна быть одна-единственная явная цель. Никогда не создавайте переменных tmp, выполняющих несколько разных вспомогательных функций во всем коде. Используйте переменную только с одной целью. Переменные, в названии которых используется tmp или temp, почти всегда либо бессмысленные и ненужные, либо неправильно названы.
Объявляйте переменные как можно ближе к месту их первого использования. Старайтесь сразу же инициализировать переменные. Если переменная используется только внутри функции, она должна быть локальной для функции. Если только внутри цикла, она должна быть локальной для цикла. Никогда не делайте глобальных переменных. Локальные переменные блока предпочтительнее по сравнению с локальными переменными функции, локальные переменные функции — по сравнению с переменными-членами класса, а последние — по сравнению с глобальными переменными. Стремитесь сократить «время жизни» каждой переменной: чем меньше время жизни переменных, тем меньше переменных приходится одновременно держать в голове при чтении и написании кода. Исследования показывают, что человек может эффективно держать в памяти не более 5-7 переменных одновременно. Большее количество неизбежно приводит к ошибкам.
Разделяйте программу на ввод, решение и вывод, это делает ваш код более модульным. Способы ввода и вывода часто меняются. У нас используются стандартные потоки и определенный описанный формат, в следующий раз те же данные могут быть записаны в файле или в базе данных в другом формате, затем они же могут поставляться уже в виде переменных в более сложной программе, которая использует ваш алгоритм в качестве подпрограммы. Записывайте вход в отдельные переменные и результат работы — в отдельные. Для их заполнения и вывода напишите отдельные функции. В частности, ваш код становится легче тестируемым, что является важным свойством. Вы можете написать альтернативное решение и сравнить его с вашим, можете запустить стресс-тест. Вообще это две принципиально разные области ответственности: ввод-вывод и преобразование данных. Не смешивайте в одном классе или функции несколько разных областей ответственности: один класс отвечает ровно за одну область. Иначе он разрастается, становится слишком сложным, а две разные области ответственности начинают быть слишком сильно связанными. Это плохо, потому что чем более независимы разные части программы, тем меньше поводов для ошибок и тем проще тестировать части программы по отдельности.
Никогда не используйте «магические константы» в коде. Если у вас где-то в коде встречаются, например, 'a' и 'z', означающие минимальный и максимальный символ алфавита, то их надо заменить на именованные константы. Например так:
```
const char kMinLetter = 'a';
const char kMaxLetter = 'z';
...

for (char letter = kMinLetter; letter <= kMaxLetter; ++letter) {
    ...
}
...
```
Пишите комментарии только по делу. В идеальном случае лучше обходиться вообще без них — ваш код прокомментирует сам себя. Конечно, так редко удается, поэтому комментарии к классам и функциям бывают полезными. Не нужно оправдывать плохое имя (см. следующий раздел) подробным комментарием. Если у вас встречается объявление вида
```
int n;  // number of balls in the bucket
```
то нужно заменить его на int number_of_balls; или int numBallsInBucket; в зависимости от принятого стиля, от того, бывают ли шары не в корзине, и от контекста. Писать комментарий следует над тем, к чему он относится. Комментарии в конце строки значительно удлиняют ее, поэтому ухудшают читаемость. При этом желательно, чтобы строка влезала в 100 символов, а зачастую бывает жесткое ограничение по длине строки (как в нашей системе проверки). Если вы все же пользуетесь комментарием в конце строки, то отделяйте его двумя пробелами от кода. Если вы решили снабдить свой код подробными комментариями, указывайте в них то, что будет интересно читающему. Для класса это описание того, для чего класс нужен, как им пользоваться. Для функции и метода — что они делают, что возвращают, что принимают на вход, какие исключения могут бросать. Вот пример хорошего комментария к функции.
```
/* Applies per symbol transformation to string.
* input[i] is transformed into transform[input[i]].
* If transform map doesn't contain input[i] and default_symbol isn't null,
*   input[i] is transformed to default_symbol.
* If transform map doesn't contain input[i] and default_symbol == 0,
*   function throws TransformError.
*/
string transformString(
    const std::string& input,
    const std::map<char, char>& transform,
    const char default_symbol);
```

Имена

У каждой создаваемой сущности в коде есть имя. Сперва автор, а впоследствии, и все читающие код ассоциируют имена с сущностями, которые они обозначают. Чтобы в каждый момент точно понимать, что в переменной хранится, чтобы быть уверенным в том, что вызов функции вернет ожидаемое значение, имена нужно давать осмысленные и грамотно определенные.

Имена переменных должны быть длинными и понятными. Каждый раз, когда вы пишете одно-двух-буквенное название переменной или используете что-то вроде cur, должно возникать неприятное чувство. Единственное место, где можно позволить себе однобуквенные переменные, — в качестве счетчика в очень коротком for'е без вложенных циклов. И то, у вас должны быть серьезные опасения, когда вы это делаете, вы должны делать это осознанно. Иначе можно легко допустить ошибку с индексами, например перепутать i с j, что происходит постоянно, если называть так переменные. Искать такую ошибку вы будете несколько часов или дней. Даже если в описании задачи есть названия R и L, это не значит, что в программе нужно их так называть. Стиль математического текста очень сильно отличается от стиля кода программы. В математическом тексте есть очень много слов, описывающих формулы и то, что в них происходит. В самих формулах ценится краткость. В коде же наоборот, слов, описывающих происходящее, практически нет. Код должен описывать сам себя, названиями переменных, методов и классов. Поэтому названия должны быть очень прозрачными. Не должно быть нужно возвращаться и смотреть вверх в объявление переменной или смотреть на ее инициализацию, чтобы понять, что она в себе содержит. Никогда не называйте переменные something1 и something2, так как очень легко ошибиться и попасть по соседней клавише, тем самым очень легко сделать баг, а искать его будет тяжело. Используйте something_first и something_second или что-нибудь еще. Как выбрать понятное название переменной? Сперва нужно описать переменную на английском (так чтобы из описания было понятно, что хранит переменная), а далее выбирать название исходя из соображений компромисса между длиной и понятностью. (3-5 слов в названии — это нормально).
Все, что относится к именам переменных, относится и к именам функций, классов и методов. Кроме того, в названиях методов (функций) обязательно должен быть глагол, описывающий действие, которое выполняет метод. Это действие должно быть одно. У каждой функции должна быть одна ясная цель. Если вы понимаете, что не можете придумать название функции без слова And (например, readFromFileAndSort), значит, функция выполняет две разные цели, и скорее всего, ее нужно разбить на несколько меньших функций (readFromFile и sort), и из внешней вызывать подряд внутренние.
Не сокращайте слова в названиях. Это ухудшает читаемость кода, а также делает невозможным поиск по нему. Не нужно сокращать index до ind или idx, current — до cur и т.д. Единственное исключение — общепринятые сокращения типа Http и т.д.
Выделяйте названия приватных членов классов, это позволяет отличить их от аргументов методов. Наиболее распространенными способами являются подчеркивание в конце: name_, — или префикс m_: m_name. Начинать имя переменной с подчеркивания не принято; следует помнить о том, что имена, начинающиеся на два подчеркивания или подчеркивание и заглавную букву, зарезервированы стандартом, и использовать их нельзя.

Продвинутые замечания

Не оптимизируйте преждевременно. Ваш алгоритм должен иметь правильную асимптотическую сложность, чтобы иметь шансы пройти в Time limit. Он должен правильно работать, чтобы не получить Wrong answer. Это два основных тезиса. Не нужно оптимизировать с целью ускорить программу в константу раз, если это хоть сколько-нибудь усложняет код. Старайтесь сделать свое изначальное решение максимально простым. Оптимизировать нужно только после того, как вы четко замерили время работы программы, убедились, что оно слишком большое, определили, какая именно функция создает узкое место. Даже суперпрофессионалы не берутся заранее предсказывать узкие места системы: в наше время, когда компиляторы умеют делать сумасшедшие оптимизации, это практически невозможно предугадать. Поэтому профессионалы и не пытаются делать это заранее и оптимизировать что-либо заранее. Сначала измерьте, найдите узкое место, а потом уже пытайтесь его оптимизировать. Все вышесказанное относится к выносу переменных из цикла для ускорения, к перебору не до n, а до n / 2 и т.д. — не нужно ничего из этого сделать. Напишите максимально простое решение, добейтесь правильной его работы, и если вдруг после этого оно окажется слишком медленным — только тогда оптимизируйте. Ваша задача в программах, которые вы пишете на этом курсе, — написать наиболее простой, понятный, читаемый и гибкий код, среди тех, которые проходят в ограничения по времени и памяти. Помните об этом и не оптимизируйте, жертвуя простотой и удобством.

Как сдавать домашние задания

На курсе есть несколько видов активностей, которые влияют на вашу оценку:

Контесты (домашние задания в системе Яндекс.Контест)
КДЗ
Тесты
Экзамен

Домашние задания в контесте

Код программ, которые вы будете сдавать в рамках нашего курса, будет проверяться автоматически в системе Яндекс.Контест.

Требования к вводу-выводу

Программа должна читать из стандартного входа и писать в стандартный выход. Входной формат гарантируется: будет так, как описано в условии. Строго придерживайтесь выходного формата. Лишние пробелы и лишние переводы строк — не страшно, а вот пропустить пробел, вывести не в том порядке, пропустить перевод строки или вывести что-то лишнее — будет являться ошибкой.

Вердикты по задаче

Система выдает один из следующих результатов на каждый запуск.

OK — задача прошла успешно.
PCF — Precompile check failed — code style violation, вы нарушили какие-то из требований по оформлению кода. Чтобы узнать, какие именно, нажмите на ссылку «отчёт» (она появляется при наведении курсора на строку посылки) и почитайте. Также вы можете получить такую ошибку, если использовали при реализации какую-нибудь стандартную структуру данных или какой-нибудь стандартный алгоритм из библиотеки STL, который в данной задаче было использовать запрещено.
CE — Compilation Error — ваша программа не компилируется на сервере. Чтобы узнать, почему, нажмите на ссылку «отчёт» (она появляется при наведении курсора на строку посылки) и посмотрите, какие ошибки нашел компилятор.
WA — Wrong Answer — на некотором тесте программа выдала неверный ответ. Вам не предоставляется возможность увидеть содержимое теста (если это тест не из условия). Внимательно посмотрите на ограничения в задаче, попробуйте придумать свой тест, на котором ответ будет неправильный.
PE — Presentation Error — ошибка представления. Например, просили вывести число, а выведена строка. В этом случае вы можете получить Wrong Answer либо Presentation error, это не гарантируется заранее.
TL — Time Limit exceeded — ваша программа работает слишком долго. Значит, у вас неправильное асимптотически решение, так как таймлимиты будут выставляться в 1,5–2 раза больше, чем время работы авторского решения на максимальном тесте, и этого должно хватать любому правильному решению.
ML — Memory Limit exceeded — ваша программа использует слишком много памяти.
RE — Runtime Error — произошла ошибка выполнения. Неочевидные возможные причины: чтение из файла вместо стандартного ввода; запись в файл вместо стандартного вывода; переполнение стека. Очевидные причины: выход за границы массива, деление на ноль.

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

Сроки

Мягкий дедлайн ставится на дату примерно через 11 суток с момента выдачи контеста.

За каждый день просрочки мягкого дедлайна отправленной посылки по задаче ставится -2 балла этой посылке. При этом берется максимум из 0 и полученного данным образом балла.

То есть жесткий дедлайн – мягкий дедлайн + 4 дня. За посылки, отправленные после жесткого дедлайна соответственно ставится 0.

Все дедлайны будут прописаны в канале курса в telegram.

Критерии оценки обычных контестов

Нет решения — 0 баллов (база)
Несоответствие кодстайлу 0 баллов итог
Прохождение тестов из условия + 1 балл
Online-тестирование + 7 баллов, в зависимости от групп в задаче
Offline-тестирование + 2 балла

Пункт 3 проверяется только при прохождении тестов из условия.

Пункт 4 проверяется только при прохождении всех тестов из online-групп.

Оцениваться группы в пунктах 3-4 могут по-разному:

два режима прерывания групп: при первой ошибке в группе (оставшиеся тесты в группе не проверяются) и без прерываний. По умолчанию до offline-проверки включен режим "при первой ошибке". Во время offline-проверки все решения пересуживаются уже со вторым режимом.
два режима оценивания групп: "полный_балл_за_группу * пройденные_тесты_в_группе/тесты_в_группе" и "0 или полный_балл_за_группу". Второй режим включается для задач на написание какого-то алгоритма (к примеру, "напишите сортировку слиянием"). Первый режим включается для задач всех остальных типов, если не написано иное.

Пункты 3 и 4 не фиксируют кол-во баллов. От задачи к задаче разбалловка баллов в 3 и 4 может меняться.

При выявлении списывания списанная задача обнуляется всем участникам списывания. Если в контесте > 1 списанной задачи, то зануляется весь контест.

При использовании читерства в задаче она также зануляется (к примеру, в контесте / задаче явным образом запрещалось использовать std::sort или что-то аналогичное, а Вы взяли и заюзали каким-то хитрым образом).

Если Вы не согласны с результатом проверки, то можете проапеллировать результат, написав на почту. В чат курса / лички ассистентов / преподавателей писать не надо.

КДЗ

TODO

Тесты

TODO

Экзамен

TODO

Как настроить окружение на своем компьютере

Введение

С недавнего времени на сервере используется новая схема тестирования решений, а точнее, отлавливается большее число ошибок за счет использования других ключей компиляции. Цель этой заметки — помочь вам получить такой же эффект на своей системе.

Помимо этого, описанные здесь рекомендации позволят вам организовать более качественное тестирование кода.

На сервере компилируется 2 варианта вашего решения, а именно:

g++-8 solution.cpp -fuse-ld=gold -fsanitize=address,undefined -fno-sanitize-recover=all -std=c++17 -O2 -Wall -Werror -Wsign-compare -o debug_solution
g++-8 solution.cpp -std=c++17 -O2 -o fast_solution

Здесь стоит отметить следующее:

-Wall и -Werror. Первый флаг заставляет компилятор выдавать дополнительные предупреждения, второй — трактовать любое предупреждение как ошибку компиляции. Таким образом, ваш код не должен давать ни одного предупреждения.
-O2 включает оптимизации кода.
-std=c++17 нужен для использования стандарта C++17.

Во втором случае решение компилируется с включенными санитайзерами. Любое обращение за пределы массива, знаковое переполнение целочисленных типов и любые подобные проявления некорректной работы с памятью и undefined behavior будут вызывать ошибку времени выполнения и приводить к вердикту Runtime Error на сервере, а не ситуации, когда ваша программа иногда работает, а иногда нет.

Любое обращение за пределы массива, знаковое переполнение целочисленных типов и любые подобные проявления некорректной работы с памятью и undefined behavior будут вызывать ошибку времени выполнения и приводить к вердикту Runtime Error на сервере, а не ситуации, когда ваша программа иногда работает, а иногда нет.

Обратите внимание, что -fsanitize=address также включает детектор утечек памяти. Поэтому, помимо контроля над тем, куда обращается ваша программа, на сервере также производится проверка, что в вашей программе нет утечек памяти (сделали new и не сделали delete). В подавляющем большинстве случаев вам вообще не нужно оперировать с динамической памятью вручную (например, для создания массивов используйте стандартные контейнеры вроде std::vector, которые правильно обращаются с памятью).

Поскольку санитайзеры вносят заметный оверхед в решение (значительно увеличивается потребляемая память и в несколько раз может возрасти время исполнения), то они используются только для запуска в задачах с большим потреблением памяти на маленьких тестах (обычно только на онлайн тестах), чтобы правильные решения не могли получить вердикты ML или TL.

Компилируется и запускается всё на Intel(R) Xeon(R) CPU E5-2660 @ 2.20GHz, 20480KB cache, virtualizаtion on 1 core, 4GB RAM с Linux-ом.

Примеры кода

Давайте рассмотрим на примерах, как работает компилятор с указанным выше набором флагов. В этом разделе приведены комментарии по поведению gcc и clang в Linux с включенными санитайзерами. Про другие ОС см. секции ниже.

Здесь происходит знаковое переполнение при вычислении BAD_MAX_INT, что порождает соответствующее предупреждение. В десятой строке происходит сравнение int и size_t, что также порождает предупреждение. Никогда не игнорируйте это предупреждение: при таком сравнении int приводится к беззнаковому типу, таким образом, неравенство -1 > size_t всегда выполнено. Этот код не компилируется с флагом -Werror.

#include <iostream>
#include <vector>

const int BAD_MAX_INT = (1 << 31) - 1;

int main() {
    size_t n;
    std::cin >> n;
    std::vector<int> data(n);
    for (int i = 0; i < data.size(); ++i) {
        std::cin >> data[i];
    }
    return 0;
}

В этом примере происходит очевидный выход за пределы массива. Если заменить динамический массив на std::vector, произойдет то же самое. И gcc, и clang успешно отловят данную ошибку с включенным флагом -fsanitize=address.

#include <iostream>
#include <vector>

int main() {
    size_t n;
    std::cin >> n;
    int *data = new int[n];
    for (size_t i = 0; i < n; ++i) {
        std::cin >> data[i];
    }
    std::cout << data[n] << '\n';
    delete[] data;
    return 0;
}

В этом примере есть утечка памяти (нет delete[]).

#include <iostream>
#include <vector>

int main() {
    size_t n;
    std::cin >> n;
    int *data = new int[n];
    for (size_t i = 0; i < n; ++i) {
        std::cin >> data[i];
    }
    return 0;
}

Здесь возникает undefined behavior при переполнении (введем 2000000000 2000000000), который отловят и clang, и gcc с включенным флагом -fsanitize=undefined.

#include <iostream>

int main() {
    int a, b;
    std::cin >> a >> b;
    std::cout << a + b << '\n';
    return 0;
}

Настройка на своей системе

Мы рекомендуем использовать среду CLion для разработки. Всем студентам ВШЭ предоставляется бесплатная лицензия. Вы можете работать из любой ОС, однако добиться поведения, описанного выше, можно только на Linux и Mac OS. Опыт показывает, что отлавливать ошибки c обращениями за пределы массива, знаковым переполнением целочисленных типов и любыми подобными проявлениями некорректной работы с памятью и undefined behavior с использованием Windows достаточно мучительно, поэтому лучше заранее озаботиться установкой Linux. Самый удобный вариант — развернуть VirtualBox. Если же у вас Windows 10, то еще одним вариантом будет установка WSL и его интеграция с CLion.

Ниже приведена инструкция для CLion.

Windows

На Windows без использования WSL санитайзеры не работают. Вы точно так же можете использовать CLion, но поддержки ASan там не будет (если только вы не настроили интеграцию с WSL, см. ссылки выше).

Linux

Создайте новый проект. Зайдите в File -> Settings -> Build, Execution, Deployment -> CMake. Изначально там будет только один профиль Debug. Когда вы нажмете + добавится профиль Release, который пригодится в дальнейшем. Добавьте еще один профиль, назовите его ASAN. В CMake Options запишите

-DCMAKE_BUILD_TYPE=ASAN

Отредактируйте ваш CMakeLists.txt. Он будет выглядеть примерно так:

cmake_minimum_required(VERSION 3.24)
project(your_project)

set(CMAKE_CXX_STANDARD 17)

set(CMAKE_CXX_FLAGS_ASAN "-g -fsanitize=address,undefined -fno-sanitize-recover=all"
        CACHE STRING "Compiler flags in asan build"
        FORCE)

add_executable(your_project main.cpp)

Теперь вы легко можете переключаться между разными видами сборок: Debug для пошагового дебага, Release для тестирования производительности, ASan для запуска с санитайзерами.

Mac OS

По сравнению с Linux, на маке необходимо произвести ряд дополнительных действий, чтобы получить такое же поведение, как и там.

Создайте новый проект. Зайдите в CLion -> Preferences -> Build, Execution, Deployment -> CMake. Изначально там будет только один профиль Debug. Когда вы нажмете + добавится профиль Release, который пригодится в дальнейшем. Добавьте еще два профиля, назовите их ASAN и UBSAN. В CMake Options запишите

-DCMAKE_BUILD_TYPE=ASAN

-DCMAKE_BUILD_TYPE=UBSAN

соответственно.

Отредактируйте ваш CMakeLists.txt. Он будет выглядеть примерно так:

cmake_minimum_required(VERSION 3.24)
project(your_project)

set(CMAKE_CXX_STANDARD 17)

set(CMAKE_CXX_FLAGS_ASAN "-g -fsanitize=address"
        CACHE STRING "Compiler flags in asan build"
        FORCE)

set(CMAKE_CXX_FLAGS_UBSAN "-g -fsanitize=undefined"
        CACHE STRING "Compiler flags in ubsan build"
        FORCE)

add_executable(your_project main.cpp)

Далее, по умолчанию на маке стоит clang. Также gcc симлинкается на clang. Но системный clang, к сожалению, не поддерживает санитайзеры (при запуске ASAN / UBSAN) упадет с ошибкой "detect_leaks is not supported on this platform". Поэтому нам нужно будет установить собственные компиляторы. Далее приведен гайд, как это можно сделать:

Для начала установите homebrew, если он у вас еще не установлен.

Затем выберите каким компилятором вы будете пользоваться: gcc или clang (лично я использую и рекомендую устанавливать оба; gcc на M1 не будет запускаться с санитайзерами). Дебагать в clang-е гораздо удобнее. gcc, в свою очередь, вам придется использовать во многих задачах со взломами, где вам потребуется покопаться в кишках gcc.

clang

Выполните команду

brew install llvm

Далее вам нужно найти путь до clang-а, который вместе с llvm из brew приехал. С этим вам помогут команды

brew info llvm  # выведет информацию про установленный пакет

brew --prefix llvm  # выведет путь до директории, на Intel маках обычно /usr/local/bin/llvm, на M1 маках – /opt/homebrew/opt/llvm

Вас интересует clang. Зайдите в папку bin, в ней должен лежать clang.

Далее необходимо прописать путь к компилятору в настройках CLion. Для этого зайдите в CLion -> Preferences -> Build, Execution, Deployment -> Toolchains и в C++ compiler пропишите полный путь к компилятору.

gcc

Выполните команду

brew install gcc

Чтобы посмотреть на версию установленного компилятора, выполните команду

brew info gcc  # выведет информацию про установленный пакет

Чтобы проверить, что gcc установился правильно, выполните (12 нужно заменить на версию gсс, установленную brew):

g++-12 --version  # выведет полную версию g++
which g++-12  # выведет полный путь к компилятору, например /usr/local/bin/g++-12 или /opt/homebrew/bin/g++-12

Далее, обратите внимание, что по умолчанию под маком ASan не включает проверку на утечки памяти. Чтобы этого избежать, зайдите в CLion -> Preferences -> Build, Execution, Deployment -> Dynamic Analysis Tools -> Sanitizers и в конце строчки AddressSanitizer (если там что-то уже написано, то через пробел) допишите строчку

detect_leaks=1

Теперь вы легко можете переключаться между разными видами сборок: Debug для пошагового дебага, Release для тестирования производительности, ASan для отлавливаний ошибок с памятью (в том числе и memory leak-ов) и UBSan для отлавливаний undefined behavior.

Проверка на соответствие стайлгайду и форматирование кода

Инструкция ниже для Linux и Mac OS.

Вам понадобятся утилиты clang-format и clang-tidy, они обычно есть в стандартных репозиториях (apt-get install или brew install). Для clang-format вы можете взять конфиг отсюда, а для clang-tidy отсюда.

Положите эти файлы в директорию с кодом или в домашнюю директорию.

Для форматирования кода выполните

clang-format -i main.cpp

Вы также можете настроить автоматическое форматирование кода с помощью этой утилиты в CLion.

Для дополнительных проверок на именование переменных, функций и прочего выполните

clang-tidy main.cpp -- -std=c++17

По умолчанию, когда лежит .clang-tidy в директории с кодом или в домашней директории, CLion подсвечивает неправильное именование переменных, функций и прочего как ошибки.

Полезное

Автоматический сбор файла из нескольких файлов

Допустим, у вас имеется два файла:

// tree.cpp
#include <iostream>

class Tree {
    // your code
};

// solution.cpp
#include <iostream>
#include "tree.cpp"

int main() {
    // your code
}

В задаче требуется отправить лишь один файл, который должен содержать несколько различных реализованных классов. И мы хотим сделать так, чтобы писать объявление каждого класса отдельно от реализации. К счастью, возможно автоматически собрать файл, который будет содержать весь необходимый код.

Для этого

Создайте директорию system-headers.

Создайте файл system-headers/iostream с следующим содержимым:

#ifndef SYSTEM_HEADERS_iostream
#define SYSTEM_HEADERS_iostream
_include_ <iostream>
#endif

Выполните следующую команду:
```
g++-12 -std=c++17 -E -P -C -nostdinc -nostdinc++ -I system-headers -D _include_=#include solution.cpp -o output.cpp
```
Здесь стоит отметить следующее:
1. -std=c++17 нужен для использования стандарта C++17. Если вы не особо обращаете внимание на используемый стандарт, то можете продолжать это делать и писать, как раньше. Остальные могут использовать все фишки нового стандарта.
2. -E отвечает за то, чтобы останавливаться после этапа препроцессинга (без дальнейшей компиляции и запуска). Возвращает предварительно обработанный исходный код, который отправляется на стандартный вывод.
3. -P запрещает компилятору добавлять номера строк во время препроцессинга.
4. -C отвечает за то, чтобы оставить комментарии. Обычно они вырезаются на этапе препроцессинга, но мы их хотим оставить.
5. -nostdinc -nostdinc++ запрещает компилятору искать заголовочные файлы (в угловых скобках) в своих папках.
6. -I system-headers объясняет компилятору, что искать объявления наших заголовочных файлов надо в нашей папке system-headers.
7. -D _include_=#include заменяет во всём коде текст _include_ на #include. Если хочется давать переменным такое имя, то решение легко адаптируется.
При необходимости, замените путь solution.cpp и output.cpp
Отформатируйте полученный файл: clang-format -i output.cpp. Практически гарантированно, что без этого контест его не примет.
Рекомендую проверить, что output.cpp компилируется и работает. После этого можно загружать его в контест.

В случае, если вы используете какие-то другие заголовочные файлы (кроме <iostream>), то нужно создавать аналогичные файлы в директории system-headers. Важны несколько моментов:

Имя файла должно в точности совпадать с именем подключаемого заголовочника. Если подключаете <math.h>, то надо создать system-headers/math.h
В этом файле пишется _include_ <…> без решёток.
include guard хотя и не обязателен, но крайне желателен. Он позволяет избежать дублирования инклюдов в результирующем файле.

Что делать, если решение не проходит в контесте

Если решение работает локально, а в контесте падает, стоит поискать тест, на котором решение работает неправильно или медленно. Для этого можно запускать стресс-тесты под санитайзерами.

Ниже перечислены основные причины, почему решение может работать медленно или потреблять много памяти

Медленный ввод-вывод

По умолчанию в C++ для iostream включен режим совместимости с stdio, который позволяет одновременно использовать оба интерфейса для ввода/вывода. В этом режиме производительность std::cin и std::cout понижается в несколько раз. Поэтому если размер ввода/вывода имеет порядок от 100 000 чисел, вам нужно будет отключить этот режим. Делать это нужно до совершения каких-либо операций ввода-вывода, желательно первой же строкой в программе:

#include <iostream>

int main() {
    std::ios_base::sync_with_stdio(false);
    ...
    return 0;
}

Также обратите внимание на то, что std::cout может работать слишком медленно, если вы выводите порядка 100 000 чисел или более, и при этом у std::cout регулярно очищается буфер. Буфер очищается при каждом выводе std::endl, так что в случае большого вывода лучше выводить "\n" вместо std::endl. Также буфер std::cout очищается при каждом вводе через std::cin — это связано с тем, что при пользовательском вводе-выводе через обычный std::cin и std::cout в консоли, необходимо показать пользователю последний вывод и очистить буфер перед тем как запрашивать очередной ввод. Эта проблема для задач с большим выводом решается с помощью вызова std::cin.tie(nullptr); в самом начале программы. Выполнение всех этих рекомендаций приведёт к тому, что ввод-вывод при помощи потоков std::cin и std::cout будет работать не медленнее ввода-вывода через printf и scanf на задачах с большим вводом-выводом. Подробнее см. здесь.

Санитайзеры на небольших тестах

В контесте ваше решение на небольших тестах запускается с санитайзером. Санитайзер увеличивает время работы и потреблении памяти программы, поэтому если в решении выделять статический массив максимального размера (например, int arr[100500]), то решение может упасть с ML.

Algorithms and Data Structures

Ссылки

FAQ

Стайлгайд

Основные правила

Синтаксис

Язык C++

Организация кода

Имена

Продвинутые замечания

Как сдавать домашние задания

Домашние задания в контесте

Требования к вводу-выводу

Вердикты по задаче

Сроки

Критерии оценки обычных контестов

КДЗ

Тесты

Экзамен

Как настроить окружение на своем компьютере

Введение

Примеры кода

Настройка на своей системе

Проверка на соответствие стайлгайду и форматирование кода

Полезное

Автоматический сбор файла из нескольких файлов

Что делать, если решение не проходит в контесте

Медленный ввод-вывод

Санитайзеры на небольших тестах