1. Идея

Нужно найти все пары уроков, которые конфликтуют.

Конфликт возможен только тогда, когда у двух уроков совпадают:

• день d;
• номер пары p.

А уже внутри одного и того же временного слота конфликт есть, если совпадает хотя бы одно из двух:

• teacher;
• room.

Поэтому удобно разбить все уроки по слотам времени. Всего слотов очень мало: 5 * 8 = 40.

Дальше для каждого слота отдельно:

• сгруппируем уроки по учителю;
• сгруппируем уроки по кабинету;
• все пары внутри каждой группы добавим в ответ.

Но есть важная деталь: одна и та же пара уроков может попасть сразу по двум причинам — и по одинаковому учителю, и по одинаковому кабинету. Значит, внутри одного слота нужно убирать дубликаты пар. Для этого удобно использовать set.

2. Наблюдения

Наблюдение 1. Уроки из разных слотов никогда не конфликтуют

Если у уроков разные d или разные p, то по условию конфликта быть не может.

Значит, задачу можно решать независимо для каждого из 40 слотов.

Наблюдение 2. Предмет subject вообще не влияет на ответ

Он есть во входных данных, но конфликт определяется только по:

• времени;
• учителю;
• кабинету.

Поэтому subject нужно только считать, но дальше можно не использовать.

Наблюдение 3. Все уроки считаются отдельными, даже если записи одинаковые

Если два урока полностью одинаковы, но идут разными строками во входе, это всё равно два разных урока с разными номерами.

Например, если дважды встретилась одна и та же запись в одном слоте, то это уже конфликтующая пара.

Наблюдение 4. Пары нужно выводить в лексикографическом порядке

То есть сначала по i, а при равенстве по j.

Поэтому после сбора всех пар достаточно отсортировать массив пар.

3. Алгоритм

Будем точно следовать эталонному решению.

Шаг 1. Разбиваем уроки по слотам

Создадим массив slots из 40 списков.

Для урока с параметрами d и p номер слота вычислим так:

slot = (d - 1) * 8 + (p - 1)

Это даёт числа от 0 до 39.

В каждый слот сохраняем:

• номер урока id;
• teacher;
• room.

Шаг 2. Обрабатываем каждый слот отдельно

Для каждого слота создаём два словаря:

• by_teacher: учитель -> список номеров уроков;
• by_room: кабинет -> список номеров уроков.

Проходим по всем урокам этого слота и раскладываем их в обе структуры.

Шаг 3. Строим конфликтующие пары

Внутри текущего слота создаём local_pairs — множество пар.

По учителям

Для каждого учителя берём список его уроков ids.

Если в списке m уроков, то все пары:

• (ids[0], ids[1])
• (ids[0], ids[2])
• ...
• (ids[m-2], ids[m-1])

являются конфликтами.

Добавляем их в local_pairs.

По кабинетам

Точно так же для каждого кабинета строим все пары уроков в его списке и тоже добавляем в local_pairs.

Использование множества важно, потому что одна и та же пара может появиться дважды:

• из-за одинакового учителя;
• из-за одинакового кабинета.

Шаг 4. Переносим пары в общий ответ

Все пары из local_pairs добавляем в массив answer.

Шаг 5. Сортируем и выводим

Сортируем answer и печатаем:

• сначала количество пар;
• затем сами пары.

4. Почему это работает

Докажем, что алгоритм находит все и только все конфликтующие пары.

Почему каждая найденная пара действительно конфликтует

Рассмотрим пару, которую алгоритм добавил в ответ.

Она появилась внутри некоторого слота, то есть оба урока имеют одинаковые d и p.

Дальше есть два варианта:

• пара была построена из одной группы в by_teacher, значит у уроков одинаковый teacher;
• пара была построена из одной группы в by_room, значит у уроков одинаковый room.

В обоих случаях выполнено определение конфликта из условия. Значит, каждая добавленная пара корректна.

Почему ни одна конфликтующая пара не будет пропущена

Возьмём любую конфликтующую пару уроков (i, j).

По определению конфликта:

• у них одинаковые d и p, значит оба урока попадут в один и тот же слот;
• кроме того, у них совпадает либо teacher, либо room.

Если совпадает teacher, то оба номера окажутся в одном списке by_teacher, и при переборе всех пар внутри этого списка пара (i, j) будет добавлена.

Если совпадает room, то аналогично пара будет добавлена через by_room.

Значит, любая конфликтующая пара обязательно попадёт в local_pairs, а потом и в общий ответ.

Почему не возникает лишних повторов

Одна и та же пара может удовлетворять сразу двум условиям: совпадает и учитель, и кабинет.

Тогда она могла бы быть построена дважды. Но внутри слота пары кладутся в set, поэтому сохраняется только один экземпляр.

Между разными слотами повторов быть не может, потому что одна и та же пара уроков принадлежит только одному временному слоту.

Следовательно, в итоговом ответе каждая конфликтующая пара встречается ровно один раз.

5. Сложность

Пусть в каком-то слоте есть группа из m уроков с одинаковым учителем или одинаковым кабинетом. Тогда перебор всех пар внутри этой группы занимает O(m^2).

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

• Разбиение по слотам: O(n).
• Группировка внутри слотов: O(n) с дополнительными логарифмами в C++ из-за map.
• Построение пар: пропорционально числу сгенерированных пар.
• Финальная сортировка: O(k log k), где k — число конфликтующих пар.

Итого удобно описывать так:

• время: O(n + число_сгенерированных_пар + k log k);
• память: O(n + k).

Нужно понимать, что если в одном слоте очень много уроков с одним и тем же учителем или кабинетом, то сам ответ может быть очень большим, и быстрее вывести его всё равно нельзя.

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

struct Lesson {
    int id;
    string teacher;
    int room;
};

int main() {
    int n;
    cin >> n;

    vector<vector<Lesson>> slots(40);

    for (int i = 1; i <= n; i++) {
        int d, p, room;
        string teacher, subject;
        cin >> d >> p >> teacher >> room >> subject;

        int slot = (d - 1) * 8 + (p - 1);
        slots[slot].push_back({i, teacher, room});
    }

    vector<pair<int, int>> answer;

    for (int s = 0; s < 40; s++) {
        map<string, vector<int>> by_teacher;
        map<int, vector<int>> by_room;

        for (const Lesson& lesson : slots[s]) {
            by_teacher[lesson.teacher].push_back(lesson.id);
            by_room[lesson.room].push_back(lesson.id);
        }

        set<pair<int, int>> local_pairs;

        for (auto& entry : by_teacher) {
            vector<int>& ids = entry.second;
            int m = (int)ids.size();
            for (int i = 0; i < m; i++) {
                for (int j = i + 1; j < m; j++) {
                    local_pairs.insert({ids[i], ids[j]});
                }
            }
        }

        for (auto& entry : by_room) {
            vector<int>& ids = entry.second;
            int m = (int)ids.size();
            for (int i = 0; i < m; i++) {
                for (int j = i + 1; j < m; j++) {
                    local_pairs.insert({ids[i], ids[j]});
                }
            }
        }

        for (auto p : local_pairs) {
            answer.push_back(p);
        }
    }

    sort(answer.begin(), answer.end());

    cout << answer.size() << '\n';
    for (auto p : answer) {
        cout << p.first << ' ' << p.second << '\n';
    }

    return 0;
}

7. Код на Python 3

n = int(input())

slots = [[] for _ in range(40)]

for idx in range(1, n + 1):
    parts = input().split()
    d = int(parts[0])
    p = int(parts[1])
    teacher = parts[2]
    room = int(parts[3])
    subject = parts[4]

    slot = (d - 1) * 8 + (p - 1)
    slots[slot].append((idx, teacher, room))

answer = []

for lessons in slots:
    by_teacher = {}
    by_room = {}

    for idx, teacher, room in lessons:
        if teacher not in by_teacher:
            by_teacher[teacher] = []
        by_teacher[teacher].append(idx)

        if room not in by_room:
            by_room[room] = []
        by_room[room].append(idx)

    local_pairs = set()

    for ids in by_teacher.values():
        m = len(ids)
        for i in range(m):
            for j in range(i + 1, m):
                local_pairs.add((ids[i], ids[j]))

    for ids in by_room.values():
        m = len(ids)
        for i in range(m):
            for j in range(i + 1, m):
                local_pairs.add((ids[i], ids[j]))

    for pair in local_pairs:
        answer.append(pair)

answer.sort()

print(len(answer))
for i, j in answer:
    print(i, j)