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

@Logumanov · Регистрация: 06.03.2014

Author24 — интернет-сервис помощи студентам

Решил задачу, но выдает ошибку 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++

#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 всё вроде работает, в чем может быть проблема?

@~~raccoonlove~~ · 07.03.2014, 19:47

Контрпример:

2
4 0
3 2

@Logumanov · 07.03.2014, 19:57 **[ТС]**

3 2
4 0

Всё верно же.

@ya_noob · 07.03.2014, 20:08

Logumanov, неохота вникать в ваше решение, но я вроде вижу быструю сортировку. так? если да, то ясно почему WA: пузырек обладает свойством устойчивости, а быстрая сортировка нет. меняйте сортировку

@Logumanov · 07.03.2014, 20:13 **[ТС]**

ya_noob, спасибо, хорошо помогли!

@~~raccoonlove~~ Заблокирован
	07.03.2014, 19:47	2
	Контрпример: 2 4 0 3 2 0

@Logumanov 16 / 12 / 3 Регистрация: 06.03.2014 Сообщений: 71
	07.03.2014, 19:57 [ТС]	3
	3 2 4 0 Всё верно же. 0

@ya_noob _ 317 / 151 / 27 Регистрация: 08.10.2011 Сообщений: 432
	07.03.2014, 20:08	4
	Сообщение было отмечено Logumanov как решение Решение Logumanov, неохота вникать в ваше решение, но я вроде вижу быструю сортировку. так? если да, то ясно почему WA: пузырек обладает свойством устойчивости, а быстрая сортировка нет. меняйте сортировку 1

@Logumanov 16 / 12 / 3 Регистрация: 06.03.2014 Сообщений: 71
	07.03.2014, 20:13 [ТС]	5
	ya_noob, спасибо, хорошо помогли! 0

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

Решение