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

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

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

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

07.03.2014, 19:44. Просмотров 922. Ответов 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 всё вроде работает, в чем может быть проблема?
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.03.2014, 19:44
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача на Timus Online Judge, C++. Решена, но (C++):

Подгонка решения задачи под тесты Timus Online Judge, С++ - C++
На Timus Online Judge столкнулся с довольно простой задачей, с которой у меня возникли некоторые проблемы. Задача: Программист...

Простенькая задачка из Timus Online Judge(1005. Куча камней) - C++
Собственно условие: http://acm.timus.ru/problem.aspx?space=1&amp;num=1005 Моё решение: #include &lt;iostream&gt; using namespace std; void...

Задача Timus - C++
Почему не проходит тест? Может кто знает? http://acm.timus.ru/problem.aspx?space=1&amp;num=1001 #include &lt;vector&gt; int main() ...

Задача 1001 acm.timus.ru - C++
Исходные данные Входной поток содержит набор целых чисел Ai (0 ≤ Ai ≤ 1018), отделённых друг от друга произвольным количеством пробелов и...

Задача решена, но программа не работает с большими значениями - C++
Пусть An = sin(1–sin(2+sin(3–sin(4+…sin(n))…) Обозначим Sn = (…(A1+n)A2+n–1)A3+…+2)An+1 Для заданного N выведите выражение SN ...

Компьютер угадывает число. Задача решена, как считаете? (вектор и цикл) - C++
Компьютер должен угадать задуманное пользователем число с 7-ми попыток. Хотел написать с использованием циклов, а не просто перебором...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raccoonlove
Заблокирован
07.03.2014, 19:47 #2
Контрпример:
2
4 0
3 2
0
Logumanov
15 / 11 / 2
Регистрация: 06.03.2014
Сообщений: 71
07.03.2014, 19:57  [ТС] #3
3 2
4 0

Всё верно же.
0
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
07.03.2014, 20:08 #4
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Logumanov, неохота вникать в ваше решение, но я вроде вижу быструю сортировку. так? если да, то ясно почему WA: пузырек обладает свойством устойчивости, а быстрая сортировка нет. меняйте сортировку
1
Logumanov
15 / 11 / 2
Регистрация: 06.03.2014
Сообщений: 71
07.03.2014, 20:13  [ТС] #5
ya_noob, спасибо, хорошо помогли!
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.03.2014, 20:13
Привет! Вот еще темы с ответами:

Элементы заданного массива расположить в обратном порядке. Правильно ли решена задача? - C++
В общем задача такая : элементы заданного массива T(k) расположить в обратном порядке: t k,t k-1,...,t2,t1. // массив.cpp : main...

Игра в крестики нолики, задача почти решена но результат не выводится на экран - C++
Извиняюсь заранее, в этом деле я очень зеленый. Прошу отнестись с пониманием )) #include&lt;iostream&gt; #include&lt;iomanip&gt; using...

Решение СЛАУ методом простых итераций, задача решена, только написать код осталось - C++
решить СЛАУ с точностью е=10 в степени(-4) 4*x1-x2-x3=2 x1+5*x2-2*x3=4 x1+x2+4*x3=6 Система из 3-х уравнений, с 3...

Задача решена только нужна "нитра" фишки по ускорению - C++
Задача такая, создать файл заданного размера к примеру 500 мегабайтов, в него на генерировать рандомно данные а потом их отсортировать в...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
07.03.2014, 20:13
Ответ Создать тему
Опции темы

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