Overview

This problem asks you to process \(N\) event logs in chronological order, build a record list following the rule “ignore the log if it has the same code as the most recently added log,” and output the final contents of that list.

Analysis

The key point of this problem is comparing the tail of the record list (the last added element) with the current log.

As a concrete example, consider the case where the logs are 1 2 2 3 3 3 2. 1. Check 1: The list is empty, so add 1. List: [1] 2. Check 2: Different from the tail 1, so add 2. List: [1, 2] 3. Check 2: Same as the tail 2, so skip. List: [1, 2] 4. Check 3: Different from the tail 2, so add 3. List: [1, 2, 3] 5. Check 3: Same as the tail 3, so skip. List: [1, 2, 3] 6. Check 3: Same as the tail 3, so skip. List: [1, 2, 3] 7. Check 2: Different from the tail 3, so add 2. List: [1, 2, 3, 2]

As we can see, it ultimately comes down to checking only whether “the current log \(A_i\) is different from the previous log \(A_{i-1}\).”

Since the constraint allows \(N\) up to \(5 \times 10^5\), which is large, we need to solve this with an \(O(N)\) algorithm that compares elements one by one. Also, since the amount of input and output is large, it is safer to use fast I/O processing in Python.

Algorithm

1. Add the first log \(A_1\) to the result list result.
2. For each log \(A_i\) from \(i = 2\) to \(N\), repeat the following:
   • If \(A_i \neq A_{i-1}\), append \(A_i\) to the end of result.
   • If \(A_i = A_{i-1}\), do nothing (skip it).
3. Output the final contents of result separated by spaces.

Complexity

• Time complexity: \(O(N)\)
  • For \(N\) logs, we perform one comparison and one append decision each, so the processing completes in linear time.
• Space complexity: \(O(N)\)
  • To store the input data and the result list, we use memory for up to \(N\) elements.

Implementation Notes

• Fast I/O: When handling I/O of size \(N \geq 10^5\) in Python, reading all at once with sys.stdin.read().split() is faster than calling input() repeatedly.

• String concatenation: When outputting a large number of elements, using " ".join(result) to output everything as a single string at once is faster than calling print repeatedly, reducing execution time.

• Comparison target: In the code, by using input_data[i] != input_data[i-1], we compare against “the previous element in the input sequence” instead of directly referencing the tail of the list. This is equivalent to always referencing the tail of the record list.

  Source Code

import sys

def solve():
    # 入力を一括で読み込み、空白で分割してリスト化する
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return
    
    # N はイベントログの件数
    n = int(input_data[0])
    
    if n == 0:
        return

    # 記録リストの最初の要素として A_1 を追加
    # A_1 は input_data[1] に格納されている
    result = [input_data[1]]
    
    # 2番目以降のログについて、直前のログと比較して異なる場合のみリストに追加する
    # 直前のログと異なる＝記録リストの末尾と異なるため
    for i in range(2, n + 1):
        if input_data[i] != input_data[i-1]:
            result.append(input_data[i])
    
    # リストの要素を空白区切りで結合して出力
    sys.stdout.write(" ".join(result) + "\n")

if __name__ == '__main__':
    solve()

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