Overview

This is a problem where you classify \(N\) participants into two groups based on their titles — “Group A (honorific: sensei)” and “Group B (honorific: san)” — then output all members of Group A first, followed by all members of Group B. Within each group, the original input order must be preserved.

Approach

The steps needed to solve this problem are the following three:

1. Determining the honorific: If the title is teacher or doctor, append sensei to the name; otherwise (student or other), append san.
2. Grouping: Assign each participant (with their determined honorific) to either Group A or Group B.
3. Preserving order: Since the problem states “preserve the order as given in the input,” we manage each group with a list (array) and append elements to the end in the order they are encountered, thereby maintaining relative order.

Given the constraint \(N \leq 2 \times 10^5\), which is relatively large, we need an algorithm with \(O(N)\) or \(O(N \log N)\) time complexity. The operations of “appending to a list” and “concatenating lists” used here complete in \(O(N)\), which is well within the time limit.

Algorithm

1. Prepare an empty list group_a for Group A and an empty list group_b for Group B.
2. For each of the \(N\) participants in the input, repeat the following:
   • If the title is teacher or doctor: create the string name + " sensei" and append it to group_a.
   • Otherwise: create the string name + " san" and append it to group_b.
3. Output all elements of group_a, followed by all elements of group_b.

Complexity

• Time complexity: \(O(N)\)
  • Reading the data, determining each participant’s group, appending to lists, and producing the final output all run in linear time with respect to \(N\).
• Space complexity: \(O(N)\)
  • Memory proportional to the input size is used to store all participants’ names and honorifics.

Implementation Notes

• Speeding up I/O: When handling I/O on the scale of \(N=2 \times 10^5\) in Python, reading all input at once with sys.stdin.read().split() is faster than calling input() repeatedly. Similarly, rather than calling print() multiple times, it is more efficient to collect results in a list and output them all at once with "\n".join(result).

• Ensuring stability: There is no need to write your own sorting algorithm. Simply extracting elements that match each condition into separate lists in order naturally achieves “grouping while preserving the original order.”

  Source Code

import sys

def main():
    # 標準入力からすべてのデータを取得し、空白（改行含む）で分割してトークンのリストにします。
    # N=2*10^5 という制約下で、Pythonにおいてはこの方法が比較的高速です。
    data = sys.stdin.read().split()
    if not data:
        return
    
    # 最初のトークンは参加者の人数 N です。
    n = int(data[0])
    
    # 肩書きによってグループ A (teacher, doctor) とグループ B (student, other) に分けます。
    # 各グループ内では入力順を維持する必要があるため、リストに順番に追加していきます。
    group_a = []
    group_b = []
    
    # 参加者ごとのデータは、名前 Si と肩書き Ri のペアで構成されています。
    # data[1] が S1, data[2] が R1, data[3] が S2, data[4] が R2 ... となります。
    for i in range(1, 2 * n + 1, 2):
        name = data[i]
        title = data[i+1]
        
        # 肩書きに応じた敬称の決定とグループ分け
        if title == 'teacher' or title == 'doctor':
            # グループ A: 敬称は sensei
            group_a.append(name + " sensei")
        else:
            # グループ B: 敬称は san
            group_b.append(name + " san")
    
    # グループ A の全員をグループ B の全員より前に配置して出力します。
    # 各参加者の情報を改行で区切って一括で出力することで高速化を図ります。
    result = group_a + group_b
    if result:
        sys.stdout.write("\n".join(result) + "\n")

if __name__ == "__main__":
    main()

This editorial was generated by gemini-3-flash-thinking.