Что спрашивают

Даны N посещений в формате «номер спортсмена, номер точки». Один спортсмен может приходить в точку несколько раз. Нужно найти максимальную длину серии спортсменов с подряд идущими номерами, побывавших на одной точке.

Выведите длину серии и наименьший номер точки среди лучших. N ≤ 100 000, оба номера ≤ 10^6. Повторные посещения не добавляют спортсменов.

Приём решения

Преобразуем строки в пары (точка, спортсмен), уберём повторные пары через set и отсортируем. Сначала идут все спортсмены одной точки по возрастанию, затем следующая точка.

Текущая серия продолжается, только если точка прежняя, а номер спортсмена равен предыдущему плюс один. Иначе длина становится единицей. При улучшении длины обновим ответ, при равенстве выберем меньшую точку.

Почему можно проверять только соседей в сортировке? Любая серия подряд идущих номеров становится сплошным фрагментом списка своей точки. Пропуск в номерах однозначно разрывает серию. Один и тот же спортсмен в разных точках остаётся в обеих: удаляются только одинаковые пары.

Число всех посетивших точку не равно длине лучшей серии: номера 1, 2, 100 дают серию только два. Время O(N log N), память O(N).

Разбор на примере

Ввод

10
9 12
21 4
50 30
7 12
24 4
9 12
20 4
51 30
8 12
22 4

Вывод

3 4
Разбор примера по шагам
ТочкаРазличные номераЛучшая серия
420, 21, 22, 2420–22: длина 3
127, 8, 97–9: длина 3
3050, 5150–51: длина 2

Точку 4 посетили спортсмены 20, 21, 22 и 24: лучшая серия 20–22 имеет длину 3. На точке 12 серия 7–9 тоже длины 3; второе посещение номера 9 ничего не добавляет. На точке 30 серия длины 2. Из двух лучших точек выбираем меньшую, 4.

Код на Python и C++

Вход задаёт спортсмена первым, а сортируемая пара содержит первой точку. Эта перестановка нужна для группировки, но не меняет смысл выходных чисел.

В C++ set<pair<int, int>> сам убирает повторы и хранит пары по возрастанию, так что отдельная сортировка не нужна.

import sys


def solve(visits):
    ordered = sorted(set((point, athlete) for athlete, point in visits))
    previous_point = previous_athlete = -1
    run = best = answer = 0
    for point, athlete in ordered:
        if point == previous_point and athlete == previous_athlete + 1:
            run += 1
        else:
            run = 1
        if run > best or run == best and point < answer:
            best, answer = run, point
        previous_point, previous_athlete = point, athlete
    return best, answer


if __name__ == '__main__':
    data = list(map(int, sys.stdin.buffer.read().split()))
    visits = list(zip(data[1::2], data[2::2]))
    print(*solve(visits))
#include <iostream>
#include <set>
#include <utility>
using namespace std;

int main() {
    int n;
    cin >> n;
    // set хранит пары (точка, спортсмен) без повторов и сразу по возрастанию.
    set<pair<int, int>> ordered;
    for (int i = 0; i < n; i++) {
        int athlete, point;
        cin >> athlete >> point;
        ordered.insert({point, athlete});
    }
    int previous_point = -1, previous_athlete = -1;
    int run = 0, best = 0, answer = 0;
    for (auto [point, athlete] : ordered) {
        if (point == previous_point && athlete == previous_athlete + 1)
            run += 1;
        else
            run = 1;
        if (run > best || (run == best && point < answer)) {
            best = run;
            answer = point;
        }
        previous_point = point;
        previous_athlete = athlete;
    }
    cout << best << ' ' << answer << endl;
}

Типичные ошибки

  • Посчитать повторные посещения

    Серия состоит из разных спортсменов. Одна пара спортсмен–точка учитывается только один раз.

  • Продолжить серию в следующей точке

    Последовательные номера из разных точек не образуют общую серию. Проверяйте совпадение точки.

  • Выбрать точку с большим числом записей

    Много отдельных номеров с пропусками могут дать короткую серию. Важна длина непрерывного фрагмента номеров.