Overview

This problem requires dividing participants into two groups based on their titles, placing Group A (teacher or doctor) before Group B (student or other), and outputting each participant with the appropriate honorific (sensei or san).

Discussion

In this problem, participants must be classified into two groups based on their titles, with Group A placed before Group B. The key point is that the original input order must be preserved within each group. In other words, the relative order within each group must not be changed.

As a straightforward approach, we read all participants at once, separate them into different lists based on the conditions. Then, by outputting Group A’s list first followed by Group B’s list, we can satisfy the requirements.

Algorithm

1. Read the number of participants from input
2. Prepare empty lists for Group A (teacher or doctor) and Group B (student or other)
3. Read each participant’s data sequentially:
   • If the title is teacher or doctor → add (name, "sensei") to Group A
   • Otherwise → add (name, "san") to Group B
4. Output all elements of Group A in order
5. Output all elements of Group B in order

This method efficiently performs grouping and output while preserving the input order.

Complexity

• Time complexity: \(O(N)\)
  • Each participant is processed once, and each operation completes in constant time
  • Output also completes in a total of \(N\) operations
• Space complexity: \(O(N)\)
  • Group A and Group B together use memory for \(N\) elements

Implementation Notes

• The grouping condition is determined by whether the title is teacher or doctor

• Since the input order must be preserved within each group, the order of appending to the lists is important

• When outputting, the name and honorific are separated by a single space

• An efficient algorithm is chosen to handle large inputs (up to 200,000 participants)

  Source Code

import sys

def main():
    data = sys.stdin.read().splitlines()
    n = int(data[0])
    group_a = []
    group_b = []
    
    for i in range(1, n + 1):
        parts = data[i].split()
        s = parts[0]
        r = parts[1]
        
        if r == "teacher" or r == "doctor":
            group_a.append((s, "sensei"))
        else:
            group_b.append((s, "san"))
    
    for person in group_a:
        print(f"{person[0]} {person[1]}")
    
    for person in group_b:
        print(f"{person[0]} {person[1]}")

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.