Рубрики

ad2

Быстрый ввод / вывод для конкурентного программирования

В конкурентном программировании важно читать ввод как можно быстрее, чтобы сэкономить драгоценное время.

Вы, должно быть, видели различные формулировки проблемы, говорящие: « Предупреждение: Большие данные ввода / вывода, будьте осторожны с определенными языками (хотя большинство должно быть в порядке, если алгоритм хорошо спроектирован)» . Ключом к таким проблемам является использование более быстрых методов ввода / вывода.

Для быстрого ввода и вывода часто рекомендуется использовать scanf / printf вместо cin / cout. Однако вы все равно можете использовать cin / cout и достичь той же скорости, что и scanf / printf, включив следующие две строки в функцию main ():

    ios_base::sync_with_stdio(false);

Он включает или выключает синхронизацию всех стандартных потоков C ++ с соответствующими им стандартными потоками C, если он вызывается до того, как программа выполнит свою первую операцию ввода или вывода. Добавление ios_base :: sync_with_stdio (false); (что по умолчанию верно), прежде чем любая операция ввода-вывода избежит этой синхронизации. Это статический член функции std :: ios_base.

    cin.tie(NULL);

tie () — это метод, который просто гарантирует сброс std :: cout до того, как std :: cin примет ввод. Это полезно для интерактивных консольных программ, которые требуют постоянного обновления консоли, но также замедляют программу для больших операций ввода-вывода. Часть NULL просто возвращает указатель NULL.

Кроме того, вы можете включить стандартную библиотеку шаблонов (STL) с одним включением:

    #include <bits/stdc++.h>

Таким образом, ваш шаблон для конкурентного программирования может выглядеть так:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    return 0;
}

Рекомендуется использовать cout << «/ n»; вместо cout << endl ;. endl медленнее, потому что он вызывает поток очистки, который обычно не нужен (подробности см. в этом разделе). (Вам нужно будет выполнить сброс, если вы пишете, скажем, интерактивный индикатор выполнения, но не при записи миллиона строк данных.) Пишите '/ n вместо endl.

Мы можем протестировать наши методы ввода и вывода по задаче INTEST — Enormous Input Teston SPOJ. Прежде чем читать дальше, я бы предложил вам сначала решить проблему.

Решение в C ++ 4.9.2

Обычный ввод / вывод: код ниже использует cin и cout. Решение принимается со временем выполнения 2,17 секунды.

// Нормальный пример кода ввода-вывода
#include <bits/stdc++.h>

using namespace std;

int main()

{

    int n, k, t;

    int cnt = 0;

    cin >> n >> k;

    for (int i=0; i<n; i++)

    {

        cin >> t;

        if (t % k == 0)

            cnt++;

    }

    cout << cnt << "\n";

    return 0;

}

Быстрый ввод / вывод Однако мы можем добиться большего и значительно сократить время выполнения, добавив две строки. Программа, приведенная ниже, принимается со временем выполнения 0,41 секунды.

// быстрая программа ввода-вывода
#include <bits/stdc++.h>

using namespace std;

  

int main()

{

    // добавил две строки ниже

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);   

      

    int n, k, t;

    int cnt = 0;

    cin >> n >> k;

    for (int i=0; i<n; i++)

    {

        cin >> t;

        if (t % k == 0)

            cnt++;

    }

    cout << cnt << "\n";

    return 0;

}

Теперь, говоря о конкурентных соревнованиях, таких как ACM ICPC, Google CodeJam, TopCoder Open, вот эксклюзивный код для быстрого чтения целых чисел.

void fastscan(int &number)

{

    // переменная для обозначения знака входного номера

    bool negative = false;

    register int c;

  

    number = 0;

  

    // извлечь текущий символ из буфера

    c = getchar();

    if (c=='-')

    {

        // число отрицательное

        negative = true;

  

        // извлечь следующий символ из буфера

        c = getchar();

    }

  

    // Продолжаем извлекать символы, если они целые

    // т.е. значение ASCII лежит от '0' (48) до '9' (57)

    for (; (c>47 && c<58); c=getchar())

        number = number *10 + c - 48;

  

    // если отсканированный ввод имеет отрицательный знак,

    // значение входного номера

    if (negative)

        number *= -1;

}

  
// вызов функции

int main()

{

    int number;

    fastscan(number);

    cout << number << "\n";

    return 0;

}

getchar_unlocked () для более быстрого ввода в C для конкурентного программирования

Эта статья предоставлена Vinay Garg. Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Рекомендуемые посты:

Быстрый ввод / вывод для конкурентного программирования

0.00 (0%) 0 votes

ad

Adblock
detector