Таблица результатов

@behzodbek · Регистрация: 09.10.2012

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

1100. Таблица результатов
Ограничение времени: 1.0 секунды
Ограничение памяти: 16 МБ
Старое программное обеспечение для проведения соревнований использует пузырьковую сортировку для создания таблицы результатов. Однако сейчас команд слишком много, и программное обеспечение работает слишком медленно. Вас попросили написать программу, которая создаёт такую же таблицу результатов, как и старое программное обеспечение, но быстро.
Исходные данные
Первая строка входных данных содержит только целое число 1 < N ≤ 150 000 — количество команд. Каждая из следующих N строк содержит два целых числа: 1 ≤ ID ≤ 107 и 0 ≤ M ≤ 100. ID — уникальный номер команды, а M — количество решённых этой командой задач.
Результат
Вывод должен содержать N строк с двумя целыми числами ID и M в каждой. Строки должны быть отсортированы в порядке убывания M с помощью пузырьковой сортировки (или аналога).

Мой код.

Java
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
package reyting;
 
import java.util.Scanner;
import java.io.*;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintWriter pr = new PrintWriter(new OutputStreamWriter(System.out));
        int Len = sc.nextInt();
        int mas[][] = new int[Len][2];
 
        for (int i = 0; i < Len; i++) {
            mas[i][0] = sc.nextInt();
            mas[i][1] = sc.nextInt();
        }
 
        for (int j = Len; j > 1; j--) {
            for (int i = 0; i < j - 1; i++) {
                if (mas[i][1] < mas[i + 1][1]) {
                    int temp = mas[i][1];
                    mas[i][1] = mas[i + 1][1];
                    mas[i + 1][1] = temp;
                    temp = mas[i][0];
                    mas[i][0] = mas[i + 1][0];
                    mas[i + 1][0] = temp;
                }
            }
        }
 
        for (int i = 0; i < mas.length; i++) {
            pr.print(mas[i][0]);
            pr.print(" ");
            pr.println(mas[i][1]);
        }
 
        pr.flush();
 
    }
}

Пишет Время истекло. Лимит времени 1 сек. А уменя 1,05 примерно. Где у меня пропадает прозводительность?

@exiqa · 09.10.2012, 23:26

где выполняете задачи? дайте адрес, пожалуйста, хочу попробовать

@mutagen · 10.10.2012, 01:30

Сообщение от exiqa

где выполняете задачи? дайте адрес, пожалуйста, хочу попробовать

это Тимус http://acm.timus.ru/problem.as... &locale=ru

Добавлено через 1 час 42 минуты
я вот сделал такой код, но тимусу почему-то он выдаёт неправильный ответ, хотя по тестам всё ок и по времени и по памяти, смахивает на некорректную проверку в их системе

Java
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Reader;
import java.io.StreamTokenizer;
import java.io.Writer;
import java.util.ArrayList;
import java.util.Iterator;
 
public class T1100 {
    static StreamTokenizer in;
 
    public static void main(String[] args) throws IOException {
        boolean oj = System.getProperty("ONLINE_JUDGE") != null;
        Reader reader = oj ? new InputStreamReader(System.in) : new FileReader("input.txt");
        Writer writer = oj ? new OutputStreamWriter(System.out) : new FileWriter("output.txt");
        in = new StreamTokenizer(new BufferedReader(reader));
        PrintWriter out = new PrintWriter(writer);
 
        int commandCount = nextInt();
 
        MySortedSet set = new MySortedSet();
        for (int i = 0; i < commandCount; i++) {
            set.add(new Command(nextInt(), nextInt()));
            System.out.println(set.getIdx());
        }
        for (Command command : set) {
            out.write(command.toString());
        }
        out.flush();
        out.close();
 
    }
 
    static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }
 
    static class Command implements Comparable<Command> {
        private int id;
        private int m;
 
        public Command(int i, int j) {
            super();
            this.id = i;
            this.m = j;
        }
 
 
        public int getM() {
            return m;
        }
 
        @Override
        public String toString() {
            return id + " " + m + "\n";
        }
 
        @Override
        public int compareTo(Command o) {
            if ((this.m - o.m) < 0)
                return 1;
            else if ((this.m - o.m) > 0)
                return -1;
            else
                return 0;
        }
    }
 
    static class MySortedSet implements Iterable<Command> {
        private final ArrayList<Command> list = new ArrayList<Command>();
        private int idx = 0;
 
        public int size() {
            return list.size();
        }
 
        public void add(Command c) {
            for (int i = 0; i < list.size(); i++) {
                if (list.get(i).getM() < c.getM()) {
                    idx = i;
                    break;
                } else if (list.get(i).getM() == c.getM()) {
                    idx = i + 1;
                    break;
                } else
                    idx = list.size();
 
            }
            list.add(idx, c);
        }
 
        public int getIdx() {
            return idx;
        }
 
        @Override
        public Iterator<Command> iterator() {
            return list.iterator();
        }
    }
}

@behzodbek · 10.10.2012, 07:29 **[ТС]**

Твой код слишком много памяти и проца должен жрать. А мой проще но с 11 ого теста не проходит всё время Time limit exxeced типа того пишет

@exiqa · 10.10.2012, 11:42

с третьей попытки

@exiqa · 10.10.2012, 12:02

Не по теме:

что они там курят? :D

@Skipy · 10.10.2012, 12:31

Сообщение от exiqa

Не по теме:

что они там курят? :D

Не по теме:

Укуркой такого не добиться, это что-то тяжелое было.

@mutagen · 10.10.2012, 12:50

Сообщение от behzodbek

Твой код слишком много памяти и проца должен жрать. А мой проще но с 11 ого теста не проходит всё время Time limit exxeced типа того пишет

мой код скушал у них памяти аж 512 килобайт - очень много

, времени 0.032 сек, и проца он скушает по минимуму, так как данные распихиваются по листу по мере прибытия, как по дереву, так что не надо

может им просто сортировка специфическая нужна, там такие ТЗ, что решение неоднозначно.
Например:
почему должно быть отсортировано ?
26 4
22 4
если пофигу и сравнение по второму полю?
я могу сортануть так что будет
22 4
26 4
и что - результат неправильный?

@behzodbek · 10.10.2012, 15:34 **[ТС]**

Сообщение от mutagen

мой код скушал у них памяти аж 512 килобайт - очень много

, времени 0.032 сек, и проца он скушает по минимуму, так как данные распихиваются по листу по мере прибытия, как по дереву, так что не надо

может им просто сортировка специфическая нужна, там такие ТЗ, что решение неоднозначно.
Например:
почему должно быть отсортировано ?
26 4
22 4
если пофигу и сравнение по второму полю?
я могу сортануть так что будет
22 4
26 4
и что - результат неправильный?

Я тя понял и уменя тоже если балы одинковые то сортировать не будит. Почему мой код не работает. Скороее всего медленно?

@exiqa · 10.10.2012, 16:26

Сообщение от behzodbek

Почему мой код не работает. Скороее всего медленно?

да, Time limit exceeded прямо об этом говорит.

Сообщение от behzodbek

Где у меня пропадает прозводительность?

как минимум здесь

Сообщение от behzodbek

Java
1
Scanner sc = new Scanner(System.in);

@behzodbek · 11.10.2012, 23:56 **[ТС]**

Сообщение от exiqa

да, Time limit exceeded прямо об этом говорит.

как минимум здесь

КАк заменить? Что предлагаете?

@mutagen · 12.10.2012, 00:12

предлагаю содрать кусок из моего решения

Java
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Reader;
import java.io.StreamTokenizer;
import java.io.Writer;
import java.util.Set;
import java.util.TreeSet;
 
public class T1100 {
    static StreamTokenizer in;
 
    public static void main(String[] args) throws IOException {
        boolean oj = System.getProperty("ONLINE_JUDGE") != null;
        Reader reader = oj ? new InputStreamReader(System.in) : new FileReader("input.txt");
        Writer writer = oj ? new OutputStreamWriter(System.out) : new FileWriter("output.txt");
        in = new StreamTokenizer(new BufferedReader(reader));
        PrintWriter out = new PrintWriter(writer);
 
        int commandCount = nextInt();
 
        Set<Command> myset = new TreeSet<Command>();
 
        for (int i = 0; i < commandCount; i++) {
            myset.add(new Command(nextInt(), nextInt()));
        }
        for (Command command : myset) {
            out.write(command.toString());
        }
        out.flush();
        out.close();
 
    }
 
    static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }
 
    static class Command implements Comparable<Command> {
        private int id;
        private int m;
 
        public Command(int i, int j) {
            super();
            this.id = i;
            this.m = j;
        }
 
        public int getM() {
            return m;
        }
 
        @Override
        public String toString() {
            return id + " " + m + "\n";
        }
 
        @Override
        public int compareTo(Command o) {
            return ((this.m - o.m) >= 1) ? -1 : 1;
        }
 
    }
}

@exiqa · 12.10.2012, 14:42

behzodbek, я лично использовал BufferedReader + StringTokenizer

Добавлено через 4 часа 1 минуту
я вот тут провел небольшой тестик, из файла считывается и заносится в массив миллион чисел. Вот что у меня получилось:

StreamTokenizer: 0.37 sec
BufferedReader: 0.791 sec
Scanner: 5.577 sec

Кликните здесь для просмотра всего текста

Java
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
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Scanner;
import java.util.StringTokenizer;
 
 
public class ReaderTest {
    
    public static final int SIZE = 1000000;
    
    public static void main(String[] args) throws IOException {
        PrintWriter pw = new PrintWriter("input.txt");
        for (int i = 0; i < SIZE; i++) {
            pw.println((int) (Math.random() * 100));
        }
        pw.close();
        
        long start, end;
        int[] array = new int[SIZE];
 
        StreamTokenizer strt = new StreamTokenizer(new BufferedReader(new FileReader(new File("input.txt"))));
        start = System.currentTimeMillis();
        for (int i = 0; i < SIZE; i++) {
            strt.nextToken();
            array[i] = (int) strt.nval;
        }
        end = System.currentTimeMillis();
        System.out.println("StreamTokenizer: " + (end - start) / 1000. + " sec");
    
        BufferedReader br = new BufferedReader(new FileReader(new File("input.txt")));
        start = System.currentTimeMillis();
        StringTokenizer st;
        for (int i = 0; i < SIZE; i++) {
            st = new StringTokenizer(br.readLine());
            array[i] = Integer.parseInt(st.nextToken());
        }
        end = System.currentTimeMillis();
        System.out.println("BufferedReader: " + (end - start) / 1000. + " sec");
        br.close();
        
        Scanner sc = new Scanner(new File("input.txt"));
        start = System.currentTimeMillis();
        for (int i = 0; i < SIZE; i++) {
            array[i] = sc.nextInt();
        }
        end = System.currentTimeMillis();
        System.out.println("Scanner: " + (end - start) / 1000. + " sec");
        sc.close();
                
    }
 
}

@mutagen · 12.10.2012, 15:50

exiqa, всё логично, можно было и не тестировать Вы на иерархию классов просто взгляните

Новые блоги и статьи Все статьи Все блоги /
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .

@exiqa 487 / 333 / 71 Регистрация: 24.12.2011 Сообщений: 591
	09.10.2012, 23:26
	где выполняете задачи? дайте адрес, пожалуйста, хочу попробовать 0

@behzodbek 0 / 0 / 0 Регистрация: 09.10.2012 Сообщений: 4
	10.10.2012, 07:29 [ТС]
	Твой код слишком много памяти и проца должен жрать. А мой проще но с 11 ого теста не проходит всё время Time limit exxeced типа того пишет 0

@exiqa 487 / 333 / 71 Регистрация: 24.12.2011 Сообщений: 591
	10.10.2012, 11:42
	с третьей попытки Миниатюры 0

@exiqa
	10.10.2012, 12:02
	Не по теме: что они там курят? :D Миниатюры 0

@mutagen 2587 / 2260 / 257 Регистрация: 14.09.2011 Сообщений: 5,185 Записей в блоге: 18
	12.10.2012, 15:50
	exiqa, всё логично, можно было и не тестировать Вы на иерархию классов просто взгляните 0