Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Logumanov
15 / 11 / 2
Регистрация: 06.03.2014
Сообщений: 71
#1

Задача на Timus Online Judge, C++. Решена, но - C++

07.03.2014, 19:44. Просмотров 815. Ответов 4
Метки нет (Все метки)

Решил задачу, но выдает ошибку WA на 2 тесте. Не могу даже представить, в чем дело. Задача:

1100. Таблица результатов
Ограничение времени: 1.0 секунды
Ограничение памяти: 16 МБ
Старое программное обеспечение для проведения соревнований использует пузырьковую сортировку для создания таблицы результатов. Однако сейчас команд слишком много, и программное обеспечение работает слишком медленно. Вас попросили написать программу, которая создаёт такую же таблицу результатов, как и старое программное обеспечение, но быстро.
Исходные данные
Первая строка входных данных содержит только целое число 1 < N ≤ 150 000 — количество команд. Каждая из следующих N строк содержит два целых числа: 1 ≤ ID ≤ 10^7 и 0 ≤ M ≤ 100. ID — уникальный номер команды, а M — количество решённых этой командой задач.
Результат
Вывод должен содержать N строк с двумя целыми числами ID и M в каждой. Строки должны идти по убыванию M в порядке, полученном с помощью пузырьковой сортировки. http://acm.timus.ru/problem.aspx?space=1&num=1100

Моё решение:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
 
using namespace std;
 
class Team {
public:
    int id;
    int tasks;
};
 
void sort(Team* t,int m,int n) {
    Team tmp;
    int k,l;
    k=m; l=n;
    int p=(k+l)/2;
    do {
        while(t[k].tasks<t[p].tasks) k++;
        while(t[l].tasks>t[p].tasks) l--;
        if(k<=l) {
            tmp=t[k];
            t[k]=t[l];
            t[l]=tmp;
            k++;
            l--;
        }
    } while(k<l);
    if(m<l) sort(t,m,l);
    if(k<n) sort(t,k,n);
}
 
int main()
{
    int n=0;
    cin>>n;
    Team* teams = new Team[n];
    for(int i=0;i<n;i++) {
        cin>>teams[i].id;
        cin>>teams[i].tasks;
    }
    sort(teams,0,n-1);
    while(n--) cout<<teams[n].id<<" "<<teams[n].tasks<<endl;
    return 0;
}
В Visual Studio 2012 всё вроде работает, в чем может быть проблема?
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.03.2014, 19:44     Задача на Timus Online Judge, C++. Решена, но
Посмотрите здесь:

Простенькая задачка из Timus Online Judge(1005. Куча камней) C++
Задача 1001 acm.timus.ru C++
C++ Решение СЛАУ методом простых итераций, задача решена, только написать код осталось
Компьютер угадывает число. Задача решена, как считаете? (вектор и цикл) C++
Задача Timus C++
Подгонка решения задачи под тесты Timus Online Judge, С++ C++
Acm.timus Wrong answer C++
Acm.timus Wrong answer C++
C++ Элементы заданного массива расположить в обратном порядке. Правильно ли решена задача?
C++ Игра в крестики нолики, задача почти решена но результат не выводится на экран
C++ Задача решена, но программа не работает с большими значениями
C++ Задача решена только нужна "нитра" фишки по ускорению

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
raccoonlove
Заблокирован
07.03.2014, 19:47     Задача на Timus Online Judge, C++. Решена, но #2
Контрпример:
2
4 0
3 2
Logumanov
15 / 11 / 2
Регистрация: 06.03.2014
Сообщений: 71
07.03.2014, 19:57  [ТС]     Задача на Timus Online Judge, C++. Решена, но #3
3 2
4 0

Всё верно же.
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
07.03.2014, 20:08     Задача на Timus Online Judge, C++. Решена, но #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Logumanov, неохота вникать в ваше решение, но я вроде вижу быструю сортировку. так? если да, то ясно почему WA: пузырек обладает свойством устойчивости, а быстрая сортировка нет. меняйте сортировку
Logumanov
15 / 11 / 2
Регистрация: 06.03.2014
Сообщений: 71
07.03.2014, 20:13  [ТС]     Задача на Timus Online Judge, C++. Решена, но #5
ya_noob, спасибо, хорошо помогли!
Yandex
Объявления
07.03.2014, 20:13     Задача на Timus Online Judge, C++. Решена, но
Ответ Создать тему
Опции темы

Текущее время: 14:53. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru