Постарайтесь заменить, если оператор с счетчиком + = ((n% k) == 0); . это может помочь немного.

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

Вы можете прочитать каждую строку с помощью Get () и разбирать строки самостоятельно без ScanF (). (Обычно я бы не рекомендовал получить (), но в этом случае вход вход уточняется.)

Образец C программа для решения этой проблемы:

#include <stdio.h>
int main() {
   int n,k,in,tot=0,i;
   char s[1024];
   gets(s);
   sscanf(s,"%d %d",&n,&k);
   while(n--) {
      gets(s);
      in=s[0]-'0';
      for(i=1; s[i]!=0; i++) {
        in=in*10 + s[i]-'0';   /* For each digit read, multiply the previous 
                                  value of in with 10 and add the current digit */
      }
      tot += in%k==0;          /* returns 1 if in%k is 0, 0 otherwise */
   }
   printf("%d\n",tot);
   return 0;
}

Эта программа примерно в 2,6 раза быстрее, чем решение, которое вы дал выше (на моей машине).

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

Хотя ваш пример настолько прост, что я едва ли вижу, что вы можете исключить - предполагая, что это часть вопроса о последующем чтении из stdin.

Несколько комментариев к коду: В вашем примере не используются никакие потоки - нет необходимости включать заголовок iostream. Вы уже загружаете элементы библиотеки С в глобальное пространство имён, включая stdio.h вместо C++ версии заголовка cstdio, поэтому использовать пространство имён std не нужно.

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

Как вы его синхронизируете?

Одна маленькая вещь, которую вы могли бы сделать, это удалить оператор if. начать с total=n, а затем внутри цикла:

total -= int( (вход % k) / k + 1) //0, если делится, 1, если нет

Можно попробовать читать входную строку за строкой и использовать atoi() для каждой входной строки. Это должно быть немного быстрее, чем scanf, потому что Вы удаляете "сканирование" строки формата.

Хотя я сомневаюсь, что CodeChef примет это, одна возможность - использовать несколько потоков, один для обработки входов/выходов, а другой - для обработки данных. Это особенно эффективно на многоядерном процессоре, но может помочь даже с одним ядром. Например, в Windows вы используете такой код (никаких реальных попыток соответствовать требованиям CodeChef -- я сомневаюсь, что они примут его с данными о времени на выходе):

#include <windows.h>
#include <process.h>
#include <iostream>
#include <time.h>
#include "queue.hpp"

namespace jvc = JVC_thread_queue;

struct buffer { 
    static const int initial_size = 1024 * 1024;
    char buf[initial_size];
    size_t size;

    buffer() : size(initial_size) {}
};

jvc::queue<buffer *> outputs;

void read(HANDLE file) {
    // read data from specified file, put into buffers for processing.
    //
    char temp[32];
    int temp_len = 0;
    int i;

    buffer *b;
    DWORD read;

    do { 
        b = new buffer;

        // If we have a partial line from the previous buffer, copy it into this one.
        if (temp_len != 0)
            memcpy(b->buf, temp, temp_len);

        // Then fill the buffer with data.
        ReadFile(file, b->buf+temp_len, b->size-temp_len, &read, NULL);

        // Look for partial line at end of buffer.
        for (i=read; b->buf[i] != '\n'; --i)
            ;

        // copy partial line to holding area.
        memcpy(temp, b->buf+i, temp_len=read-i);

        // adjust size.
        b->size = i;

        // put buffer into queue for processing thread.
        // transfers ownership.
        outputs.add(b);
    } while (read != 0);
}

// A simplified istrstream that can only read int's.
class num_reader { 
    buffer &b;
    char *pos;
    char *end;
public:
    num_reader(buffer *buf) : b(*buf), pos(b.buf), end(pos+b.size) {}

    num_reader &operator>>(int &value){ 
        int v = 0;

        // skip leading "stuff" up to the first digit.
        while ((pos < end) && !isdigit(*pos))
            ++pos;

        // read digits, create value from them.
        while ((pos < end) && isdigit(*pos)) {
            v = 10 * v + *pos-'0';
            ++pos;
        }
        value = v;
        return *this;
    }

    // return stream status -- only whether we're at end
    operator bool() { return pos < end; }
};

int result;

unsigned __stdcall processing_thread(void *) {
    int value;
    int n, k;
    int count = 0;

    // Read first buffer: n & k followed by values.
    buffer *b = outputs.pop();
    num_reader input(b);
    input >> n;
    input >> k;
    while (input >> value && ++count < n) 
        result += ((value %k ) == 0);

    // Ownership was transferred -- delete buffer when finished.
    delete b;

    // Then read subsequent buffers:
    while ((b=outputs.pop()) && (b->size != 0)) {
        num_reader input(b);
        while (input >> value && ++count < n)
            result += ((value %k) == 0);

        // Ownership was transferred -- delete buffer when finished.
        delete b;
    }
    return 0;
}

int main() { 
    HANDLE standard_input = GetStdHandle(STD_INPUT_HANDLE);
    HANDLE processor = (HANDLE)_beginthreadex(NULL, 0, processing_thread, NULL, 0, NULL);

    clock_t start = clock();
    read(standard_input);
    WaitForSingleObject(processor, INFINITE);
    clock_t finish = clock();

    std::cout << (float)(finish-start)/CLOCKS_PER_SEC << " Seconds.\n";
    std::cout << result;
    return 0;
}

Это использует потокобезопасный класс очереди, о котором я писал много лет назад:

#ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED

namespace JVC_thread_queue { 
template<class T, unsigned max = 256>
class queue { 
    HANDLE space_avail; // at least one slot empty
    HANDLE data_avail;  // at least one slot full
    CRITICAL_SECTION mutex; // protect buffer, in_pos, out_pos

    T buffer[max];
    long in_pos, out_pos;
public:
    queue() : in_pos(0), out_pos(0) { 
        space_avail = CreateSemaphore(NULL, max, max, NULL);
        data_avail = CreateSemaphore(NULL, 0, max, NULL);
        InitializeCriticalSection(&mutex);
    }

    void add(T data) { 
        WaitForSingleObject(space_avail, INFINITE);       
        EnterCriticalSection(&mutex);
        buffer[in_pos] = data;
        in_pos = (in_pos + 1) % max;
        LeaveCriticalSection(&mutex);
        ReleaseSemaphore(data_avail, 1, NULL);
    }

    T pop() { 
        WaitForSingleObject(data_avail,INFINITE);
        EnterCriticalSection(&mutex);
        T retval = buffer[out_pos];
        out_pos = (out_pos + 1) % max;
        LeaveCriticalSection(&mutex);
        ReleaseSemaphore(space_avail, 1, NULL);
        return retval;
    }

    ~queue() { 
        DeleteCriticalSection(&mutex);
        CloseHandle(data_avail);
        CloseHandle(space_avail);
    }
};
}

#endif

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

Разделение двух больших чисел трудно. Возможно, улучшение было бы сначала охарактеризовать K немного, глядя на некоторые из более мелких простых чисел. Скажем 2, 3 и 5 на данный момент. Если k делится по любому из них, чем intornum также должен быть или ввода не делится к k. Конечно, есть больше хитростей для игры (вы могли бы использовать побитовые и ввода в inputnum до 1, чтобы определить, делится ли вы на 2), но я думаю, что просто удаление низких преслых возможностей даст разумное улучшение скорости (все равно стоительно стоит).

2,5 мб/сек - 400 фунтов/байт.

Существует два больших процесса на байт, ввод и разбиение файлов.

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

Для разбора, sscanf построен для обобщения, а не для скорости. атои должно быть довольно быстрым. Моя привычка, к лучшему или к худшему, делать это самому, как в:

#define DIGIT(c)((c)>='0' && (c) <= '9')
bool parsInt(char* &p, int& num){
  while(*p && *p <= ' ') p++; // scan over whitespace
  if (!DIGIT(*p)) return false;
  num = 0;
  while(DIGIT(*p)){
    num = num * 10 + (*p++ - '0');
  }
  return true;
}

Циклы, сначала над ведущими пробелами, затем над цифрами, должны быть почти такими же быстрыми, как машина может идти, конечно, намного меньше 400 фунтов/байт.

Скорость не определяется вычислениями - большая часть времени, которое занимает запуск программы, потребляется i/o.

Добавьте вызовы setvbuf перед первым вызовом scanf для существенного улучшения:

setvbuf(stdin, NULL, _IOFBF, 32768);
setvbuf(stdout, NULL, _IOFBF, 32768);

-- редактирование --

Предполагаемые магические числа - это новый размер буфера. По умолчанию, FILE использует буфер размером 512 байт. Увеличение этого размера уменьшает количество раз, когда библиотеке времени исполнения C++ приходится вызывать операционную систему на чтение или запись, что на сегодняшний день является самой дорогой операцией в вашем алгоритме.

Сохраняя размер буфера кратным 512, это устраняет фрагментацию буфера. Должен ли размер буфера быть 1024*10 или 1024*1024 зависит от системы, на которой он будет выполняться. Для 16-битных систем размер буфера, превышающий 32К или 64К, как правило, вызывает трудности при выделении буфера и, возможно, при управлении им. Для любой более крупной системы сделайте его размером, зависящим от доступной памяти и от того, с чем еще он будет конкурировать.

Не имея известной проблемы с памятью, выбирайте размер буферов, примерно равный размеру связанных с ними файлов. То есть, если входной файл имеет размер 250К, используйте его в качестве размера буфера. С увеличением размера буфера отдача определенно будет уменьшаться. Для примера 250К буфер размером 100К потребует три чтения, в то время как буфер размером 512 байт по умолчанию требует 500 чтений. Дальнейшее увеличение размера буфера, так как требуется только одно чтение, вряд ли приведет к значительному улучшению производительности по сравнению с тремя чтениями.