Задача на сортировку Опции

[klem4]

Есть следующая задача:

Входные данные
Дано число N (1 ≤ N ≤ 100000), а затем в одной или нескольких строках N натуральных чисел из диапазона от 1 до 100.
Выходные данные
Выведите в одной строке N чисел в неубывающем порядке.

Есть ограничения:
Лимит времени: 0.1 секунды

Понятно, что сортировать тут ничего не нужно, так как в заданное время не уложиться, есть решение:

Спойлер (Показать/Скрыть)

#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

int main()
{
    long n = 0;
    vector<long> counts(101, 0);

    cin >> n;

    int value = 0;
    while ( n-- )
    {
        cin >> value;
        ++counts[value];
    }

    stringstream ss;

    for (int i = 1; i <= 100; i++ )
    {
        for (long j = 0; j < counts[i]; j++ )
        {
            ss << " " << i;
        }
    }

    string s = ss.str();
    s.erase(s.begin());
    cout << s << endl;

    return 0;
}

Но оно проходит всего-лишь 78.6% тестов, на остальных - превышение времени, максимальное время работы 0.109 секунды из 0.1 секунды, то есть превышение в 0.009с. От куда мне их взять ума не приложу Пробовал кучу разных вариантов, без векторов, без строк, все только хуже. Нид хелп

Добавлено через 19 мин.
вопрос решен, помогла замена iostream на stdio.h

[karpinsky]

Ты всерьёз считаешь, что этот самый мультимап (внутри - дерево, т.е. это аллокации и кэш-промахи) будет быстрее сортировки подсчётом?!

А ты всерьез считаешь, что пробежаться по дереву одним циклом будет медленнее, чем организовать несколько (до 100) циклов, и в каждом из них делать что-то, а потом еще и по результирующей строке пройтись erase-ом? Сортировка сортировкой, но ее результаты надо еще обработать, и представить в нужной форме.

В общем, напиши своё решение, пошли ОПу, пусть он сравнит.

Знаешь, я вообще не обязан ничего никому посылать. Я предложил метод решения, у себя, разумеется, проверил его. На миллионе входных значений (из файла) никакого проседания (тем более - пятикратного) multimap-а не заметил, если ТС заинтересуется - сделает и проверит. Если у тебя комплятор - дерьмо - это твои личные проблемы. Интеловский компилер уделает мультимапом любую из самописных сортировок. А равняться на слабачков типа M$ или Борланд я как-то не привык.

любой, кто хочет выжать максимум из своей программы, пусть даже ценой нечитаемого кода (игрострой), первым делом отказывается от СТЛ.

Не надо мне про игрострой. STL применяется в таких проектах, что у тебя диска не хватит исходники сохранить, и никто не собирается от него отказываться (я не про игрострой, игрушки меня давно не интересуют). Единственный недостаток STL - это увеличение времени _компиляции_ программы. Времени выполнения это не касается. А коли сидеть на VC6 (или еще ниже) - так это уж дело каждого, либо переходить на современное ПО и получать выгоду, либо плестись в конце колонны в попытках хитромудрыми ухищрениями выиграть в скорости за счет потери читабельности и вообще всего, чего можно, и все равно проигрывать современным компиляторам на современных камнях.

Сообщение отредактировано: karpinsky - 22.04.2011 16:57