Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Visual C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 02.04.2017, 01:15   #1
Stasya_
Новичок
Джуниор
 
Регистрация: 02.04.2017
Сообщений: 2
По умолчанию Задача "Соревнования по бегу"

Соревнования по бегу

Имя входного файла: race.in
Имя выходного файла: race.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
В Рио-де-Жанейро перед Олимпиадой-2016 проводятся пробные соревнования по бегу. Одной из
важных задач по окончании соревнования является отображение результатов для каждой страны в
отдельности. За день до соревнования стало известно, что программное обеспечение для выполнения
этой задачи еще не готово. Ваша задача — помочь в его разработке.
Вам дана информация о том, в каком порядке участники приходили к финишу. Про каждого
участника известно, какую он представляет страну, а также его фамилия. Составьте для каждой
страны, участвовавшей в соревновании, список участников из этой страны в порядке прихода их к
финишу.

Формат входного файла
В первой строке входного файла находится число n (1 ≤ n ≤ 100 000) — число участников
соревнования. В каждой из последующих n строк находятся название страны, которую представляет
участник, и фамилия участника, разделенные ровно одним пробелом. Первым к финишу пришел
участник, приведенный в первой после числа n строке входного файла, вторым — во второй строке,
и так далее. Название страны и фамилия участника — строки длиной от одного до 10 символов,
состоящие из заглавных и строчных латинских букв.

Формат выходного файла

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


Условием этой задачи также является использование сортировки слиянием.

Вот мой код. Он не проходит тест по времени (превышение). Что нужно исправить? Ума не приложу.
Код:
#include<sstream>
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
 
vector <vector<string>> merge(vector <vector<string>> a, vector <vector<string>> b)
{
    vector<vector<string>> res(a.size() + b.size());
    int count_a = 0, count_b = 0;
 
    for (int i = 0; i < res.size(); i++)
    {
        if (count_a == a.size())
        {
            res[i] = b[count_b];
            count_b++;
            continue;
        }
 
        if (count_b == b.size())
        {
            res[i] = a[count_a];
            count_a++;
            continue;
        }
 
        if (a[count_a] <= b[count_b])
        {
            res[i] = a[count_a];
            count_a++;
        }
        else
        {
            res[i] = b[count_b];
            count_b++;
        }
    }
    return res;
}
 
vector<vector<string>> merge_sort(vector <vector<string>> a)
{
    if (a.size() == 1)
        return a;
 
    vector<vector<string>> b, c;
    b.assign(a.begin(), a.end() - (a.size() / 2));
    c.assign(a.end() - (a.size() / 2), a.end());
    return merge(merge_sort(b), merge_sort(c));
}
 
int main()
{
    ifstream in("race.in");
    ofstream out("race.out");
 
    vector<vector<string>> mass;
 
    int n;
    in >> n;
 
    for (int i = 0;i < n;i++) {
        int z = 0;
        string str1, str2;
        in >> str1 >> str2;
 
        for (int j = 0;j < mass.size();j++) {
            if (str1 == mass[j].front()) {
                mass[j].push_back(str2);
                z++;
            }
        }
        if (z == 0) {
            vector<string>a;
            a.push_back(str1);
            a.push_back(str2);
            mass.push_back(a);
        }
    }
 
    mass = merge_sort(mass);
 
    for (int i = 0;i < mass.size();i++) {
        for (int j = 0;j < mass[i].size();j++) {
            if (j == 0) {
                out << "=== " << mass[i][j] << " ===\n";
            }
            else {
                out << mass[i][j] << endl;
            }
        }
    }
}
Stasya_ вне форума Ответить с цитированием
Старый 04.04.2017, 00:56   #2
Dekay
Пользователь
 
Регистрация: 21.06.2016
Сообщений: 65
По умолчанию

У тебя квадратичная сложность, поэтому и ТЛ
Можешь просто считать все данные в формате pair<string, time>
А потом отсортировать. Даже собственный компаратор тебе не нужен будет
Dekay вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Убрать папки "Pictures", "Music", "Видео", "Downloads" из "МОЙ КОМПЬЮТЕР" Бахтиёр1916 Windows 1 05.04.2017 12:53
Нужно пояснить/прокомментировать код программы, или коды функций "Добавить" "Удалить" "Обновить(редактировать" "Поиск" "Период") ZIRASS PHP 4 15.06.2016 14:23