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

[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]

Ничего у него не страдает, если правильно использовать (в данном конкретном случае работаем не с какими-то своими хитрыми классами, на которых может быть потеря времени, а с обычным int, тут все будет в порядке). Просто для решения задачи нужно сначала подумать, а потом начинать программировать. В данном случае было принято неверное решение об использовании вектора, его придется отдельно сортировать, либо обрабатывать специальным образом, чтобы получить желаемый результат. Мультимапу же ничего подобного делать не надо, он будет содержать добавляемую информацию уже в сортированном виде (кстати, в виде того же дерева, которое предложено выше), и достаточно будет данные только перенести в строку и вывести на печать.

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

P.S. Заранее извиняюсь за вторжение на форум под названием "Все о Паскале", как раз к Паскалю и его потомкам я равнодушен, но в этом разделе может и найдется что-нибудь интересное...

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