Overview

Divide participants into two groups: “teacher/doctor” and “student/other”. Place the former group first (while preserving the input order within each group), and output each name followed by the appropriate honorific (sensei / san).

Discussion

The two key points are:

1. The reordering must be “stable”
   Group A (teacher/doctor) goes first, and Group B (student/other) goes after, but the original input order must be preserved within each group.
   For example, if the input is:

   • A1 (teacher), B1 (student), A2 (doctor)
     then the output order is:
     
   • A1, A2, B1
     The relative order of A1 and A2 must remain the same as in the input.

2. There is no need to perform a full sort (and it’s simpler not to)
   The condition “A first, B after” can be satisfied by simply distributing each element into an A array or B array, then concatenating them at the end.
   If you naively try to sort everything, you need to carefully design sort keys and ensure stability (stable sort), which tends to make the implementation more complex. Furthermore, while \(O(N\log N)\) sorting would be fast enough given \(N \le 2\times 10^5\), this problem can be straightforwardly solved in \(O(N)\).

Also, note that the output is not the title itself, but rather:
- teacher/doctor → sensei
- student/other → san

Algorithm

1. Prepare empty arrays group_a and group_b.
2. For each participant, read their title r:
   • If r is teacher or doctor, append "{name} sensei" to group_a
   • Otherwise (student/other), append "{name} san" to group_b
3. Finally, output group_a + group_b from top to bottom.
   Since elements are appended to each array in input order, the order within each group is preserved, and the groups are arranged in A→B order.

Complexity

• Time complexity: \(O(N)\) (each participant is processed exactly once)
• Space complexity: \(O(N)\) (for storing the output strings in arrays)

Implementation Tips

• Since the input can be up to \(2\times 10^5\) lines, using sys.stdin.readline makes it faster.

• Outputting with "\n".join(...) all at once is also faster.

• Writing the condition explicitly as r == "teacher" or r == "doctor" helps reduce mistakes.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    group_a = []
    group_b = []
    for _ in range(N):
        s, r = input().split()
        if r == "teacher" or r == "doctor":
            group_a.append(f"{s} sensei")
        else:
            group_b.append(f"{s} san")
    sys.stdout.write("\n".join(group_a + group_b))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.