Overview

This problem asks us to determine whether we can appropriately fill in the unclear parts (\(-1\)) of each memo so that all memos become the same integer sequence.

Analysis

Each memo has exactly one \(-1\), and all other elements are fixed. The goal is to determine whether there exists an original password \(P\) such that all memos agree.

The key observation is that for each position \(j\), we just need to check whether there are no contradictions when comparing the \(j\)-th element across all memos.

Issues with the Naive Approach

The first idea that comes to mind is to actually try completing all memos and checking if they match, but this is impractical because there are too many ways to complete them. In particular, since the values that can be substituted at \(-1\) positions range from \(0\) to \(10^9\), exhaustive search is impossible.

Solution

In fact, there is no need to complete the memos. What matters is simply “whether all fixed values at each position \(j\) are consistent.”

Specifically, for each position \(j\): - Collect the values that are not \(-1\) and verify that there is only one distinct value. - If there are 2 or more distinct values, no matter what values we substitute, we cannot make them match → No - If there is exactly 1 distinct value, that value becomes \(P_j\). - If all values are \(-1\), we can set any value (e.g., \(0\)).

In this way, if there are no contradictions at any position, the answer is Yes; otherwise, it is No.

Algorithm

1. Read each memo as input.
2. For each position \(j\) (\(0 \leq j < M\)), do the following:
   • Collect the values at that position (ignoring \(-1\)).
   • If the number of distinct collected values is 2 or more, output No and terminate.
   • If there is exactly 1 distinct value, that value is \(P_j\).
   • If there are 0 distinct values (all are \(-1\)), any value can be chosen, so it’s OK.
3. If there are no contradictions at any position, output Yes.

Complexity

• Time complexity: \(O(N \times M)\)
  We only access each element once, so it runs in linear time.
• Space complexity: \(O(N \times M)\)
  We need to store all memos.

Implementation Notes

• Since each position can be processed independently, swapping the loop order to have position \(j\) as the outer loop improves clarity.

• Using a set to manage the collection of values makes it easy to determine the number of distinct values.

• The value range (\(0\) to \(10^9\)) is automatically satisfied if there are no contradictions, so a single check at the end is sufficient.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    # メモを読み込む
    notes = []
    idx = 2
    for _ in range(N):
        note = list(map(int, data[idx:idx+M]))
        notes.append(note)
        idx += M
    
    # 各位置jについて、矛盾がないかチェックし、P_jの候補を求める
    for j in range(M):
        # 位置jにおける、-1でない値を集める
        values = set()
        missing_positions = []  # -1があるメモのインデックス
        
        for i in range(N):
            val = notes[i][j]
            if val == -1:
                missing_positions.append(i)
            else:
                values.add(val)
        
        # もし-1でない値が2種類以上あれば不可能
        if len(values) > 1:
            print("No")
            return
        
        # 値が1種類であれば、それがP_jの値
        if len(values) == 1:
            p_val = values.pop()
            if not (0 <= p_val <= 10**9):
                print("No")
                return
            # -1の箇所もこの値にできることを確認（これは常に可能）
            continue
        # valuesが空 => 全て-1 => 任意の値（例えば0）を選べばよい
        # 特に問題なし
    
    print("Yes")

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.