ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Как писать решения на C/C++

Программы на C и C++ компилируются на сервере с помощью 32-битных компиляторов: Microsoft Visual C++ 2013, MinGW GCC 4.9.1 и Clang 3.5. Отдельно поддерживаются стандарты С++11 и С++14.

Microsoft Visual C++ 2013 запускается со следующими параметрами:

// C
cl /TC /MT /EHsc /GL /O2 /W3 /Za /D "_CRT_SECURE_NO_WARNINGS" 
   /D "_CRT_SECURE_NO_DEPRECATE" /D "ONLINE_JUDGE"

// C++
cl /TP /MT /EHsc /GL /O2 /W3 /Za /D "_CRT_SECURE_NO_WARNINGS" 
   /D "_CRT_SECURE_NO_DEPRECATE" /D "ONLINE_JUDGE"

Вся необходимая документация доступна онлайн: Visual C++ Reference. Также вы можете скачать бесплатную версию Microsoft Visual Studio Express.

MinGW GCC 4.9.1 запускается со следующими параметрами:

// C
gcc -static -fno-strict-aliasing -DONLINE_JUDGE -lm -s 
    -Wl,--stack=67108864 -O2 -o %1.exe %1

// C++
g++ -static -fno-strict-aliasing -DONLINE_JUDGE -lm -s 
    -x c++ -Wl,--stack=67108864 -O2 -o %1.exe %1

// C11
gcc -static -fno-strict-aliasing -DONLINE_JUDGE -lm -s 
    -std=c11 -Wl,--stack=67108864 -O2 -o %1.exe %1

// C++11
g++ -static -fno-strict-aliasing -DONLINE_JUDGE -lm -s 
    -x c++ -std=c++11 -Wl,--stack=67108864 -O2 -o %1.exe %1

Несмотря на опцию -static программы линкуются с MSVCRT. Для повышения совместимости со стандартами C++ линковка с libmsvcrt заменена на линковку с libmsvcr110.

Вы можете скачать компилятор и документацию на официальном сайте.

Clang 3.5 работает в окружении MinGW GCC 4.9.1 и запускается со следующими параметрами:

// C++14
clang++ -static -fno-strict-aliasing -DONLINE_JUDGE -lm -s 
    -x c++ -std=c++14 -Wl,--stack=67108864 -O2 -o %1.exe %1

Вы можете скачать компилятор и документацию на официальном сайте LLVM.

Пример решения задачи

Вот пример решения задачи A + B на языке C:

#include <stdio.h>
int main()
{
   int a, b;
   scanf("%d%d", &a, &b);
   printf("%d\n", a + b);
   return 0;
}

И пример решения той же задачи на языке C++:

#include <iostream>
int main()
{
   int a, b;
   std::cin >> a >> b;
   std::cout << a + b << std::endl;
   return 0;
}

Ввод/вывод

Пример того, как надо пользоваться вводом/выводом, приведен выше. У тех, кто пишет на C++, всегда есть выбор из двух библиотек ввода/вывода — стандартного (scanf, printf) и потокового (cin, cout). Потоковый ввод/вывод удобен в использовании, но работает гораздо медленнее стандартного. Это даже может стать причиной получения вердикта Time limit exceeded. Поэтому, если вы видите, что в задаче надо считывать много входных данных (скажем, больше мегабайта) или много выводить, то не следует использовать потоковый ввод/вывод.

Не забывайте, что функции чтения символов возвращают отрицательные результаты для символов с кодами 128-255. Если во входных данных могут присутствовать такие символы, то лучше явно привести тип считанного символа к unsigned char, чем получить из-за этого вердикты Wrong answer или Runtime error (access violation).

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

#include <stdio.h>
...
// numbers
int n;
while (scanf("%d", &n) != EOF)
{
   ...
}
// lines
char line[1000];
while (gets(line))
{
   ...
}
// characters
int c;
while ((c = getchar()) != EOF)
{
   ...
}
#include <iostream>
...
// numbers
int n;
while (std::cin >> n)
{
   ...
}
// lines
std::string line;
while (std::getline(std::cin, line))
{
   ...
}
// characters
char c;
while (std::cin.get(c))
{
   ...
}

Особенности компилятора по сравнению с другими 32-битными компиляторами C/C++

Только для Visual C++. Есть некоторые особенности компилятора, используемого на сервере, которые следует знать, чтобы не получать вердикт Compilation error.

  • Нельзя вызывать функции из заголовочного файла math.h от целочисленных параметров. Такой код не скомпилируется: sqrt(2). Правильно писать sqrt((double)2) или sqrt(2.0).
  • В заголовочном файле math.h определены функции j0, j1, jn, y0, y1, yn. В результате нельзя объявлять глобальные переменные с такими именами, если используется math.h. В заголовочных файлах библиотеки STL определены функции next, prev, begin, end, rank, count, hash. Эти имена нельзя использовать для именования глобальных переменных и функций.
  • Тип long double совпадает с типом double. Т.е. sizeof(long double) = sizeof(double) = 8. Для решения задач всегда достаточно типа double (если только не требуется своя реализация чисел с плавающей точкой).
  • Не поддерживается функция itoa. Пользуйтесь функцией sprintf.
  • Область видимости переменной, объявленной в заголовке оператора for, ограничена телом этого оператора.

Как пользоваться 64-битными целыми типами данных

Компилятор полностью поддерживает 64-битные целые, как со знаком, так и без знака. 64-битное целое со знаком имеет диапазон значений от –9223372036854775808 до 9223372036854775807, без знака — от 0 до 18446744073709551615. Объявить 64-битную переменную можно следующим способом:

long long a;
unsigned long long b;

Читать и выводить 64-битные переменные также можно двумя способами в зависимости от используемой библиотеки ввода/вывода:

#include <stdio.h>
...
scanf("%lld", &a);
scanf("%llu", &b);
printf("%lld", a);
printf("%llu", b);

#include <iostream>
...
std::cin >> a;
std::cin >> b;
std::cout << a;
std::cout << b;

Библиотека STL

STL — стандартная библиотека шаблонов (Standard Template Library), неотъемлемая часть C++, предоставляющая в распоряжение программиста набор контейнеров, итераторов и алгоритмов. Умелое использование этой библиотеки помогает сократить объем кода и уменьшить время на написание программы.

Контейнеры STL представляют собой готовые реализации часто использующихся структур данных. Самыми полезными при решении задач являются:

  • динамический массив vector;
  • сортированный ассоциативный массив map и сортированное множество элементов set, основанные на красно-черных деревьях (операции удаления, вставки и поиска элементов выполняются за логарифмическое время);
  • очередь queue, очередь с приоритетами priority_queue, дек deque и стек stack.

Итератор в STL — это абстракция, позволяющая обходить элементы какого-либо контейнера. С точки зрения программиста, итератором является любой объект, поддерживающий операторы разыменования указателя на текущий элемент (*, ->) и перемещения к следующему элементу (++) (обычный указатель тоже является итератором). Все контейнеры STL предоставляют итераторы для обхода своих элементов; они доступны через обращение container_type::iterator, где container_type — это тип контейнера.

Самый часто применяемый алгоритм STL — это быстрая сортировка sort, работающая за время O(N × log N). Всего в библиотеке определено около 60 алгоритмов, включая бинарный поиск binary_search, генерацию следующей перестановки элементов next_permutation, линейный поиск find и многие другие.

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

#include <iostream>
#include <map>
#include <string>

int main()
{
   std::map<std::string, int> words;
   std::string word;

   while (std::getline(std::cin, word))
      words[word]++;
   for (std::map<std::string, int>::iterator it = words.begin(); it != words.end(); it++)
      std::cout << it->first << " - " << it->second << std::endl;

   return 0;
}

Так как операции с контейнером map выполняются за логарифмическое время, сложность решения — O(N × log N), где N — объем входных данных.

Прочие замечания

В решениях задач нельзя кидать исключения (даже внутри блока try … catch) — это будет проинтерпретировано проверяющей системой как Runtime error.

Только для Visual C++. Для того, чтобы увеличить объем стека и избежать его переполнения при использовании «глубокой» рекурсии, следует использовать специальную директиву (в примере размер стека устанавливается равным 16 МБ):

#pragma comment(linker, "/STACK:16777216")

Удобно использовать для отладки решений условную директиву ONLINE_JUDGE:

#include <stdio.h>
int main()
{
#ifndef ONLINE_JUDGE
   freopen("input.txt", "rt", stdin);
   freopen("output.txt", "wt", stdout);
#endif
   int a, b;
   scanf("%d%d", &a, &b);
   printf("%d\n", a + b);
   return 0;
}

Обратите внимание на то, что функцию freopen можно применять и при использовании потокового ввода/вывода:

#include <iostream>
int main()
{
#ifndef ONLINE_JUDGE
   freopen("input.txt", "rt", stdin);
   freopen("output.txt", "wt", stdout);
#endif
   int a, b;
   std::cin >> a >> b;
   std::cout << a + b << std::endl;
   return 0;
}

Прежние компиляторы

  • Intel C++ Compiler 7.0 использовался до 3 августа 2010 года.
  • MinGW GCC 4.7.2 использовался до 3 октября 2014.
  • Microsoft Visual C++ 2010 использовался до 22 сентября 2015.