Overview

This problem asks you to count “how many days out of \(D\) days each user visited the facility,” and output in ascending order the user numbers of those who visited on \(K\) or more days.

Analysis

The key point is to count not the “number of visits” but the “number of days visited (i.e., whether the user appears in that day’s record).” However, since this problem guarantees that “the same user is not recorded multiple times on the same day,” simply counting each user once for each day’s list they appear in directly gives us the “number of days visited.”

A naive approach like “for each user \(i\), scan through all days to check if they visited that day (e.g., linear search)” tends to result in a roundabout implementation (requiring multiple passes through the input lists). Instead, simply “incrementing the count for each user as they appear while reading the input” solves the problem cleanly and reliably.

Example: - \(D=3, K=2\) - Day 1: {1,3} - Day 2: {2,3} - Day 3: {3} → User 3 visited 3 days, User 1 visited 1 day, User 2 visited 1 day → Only “3” has \(K=2\) or more days

Algorithm

1. Prepare an array cnt of length \(N\), where cnt[i] represents “the number of days user \(i\) visited” (initialized to 0).
2. For each day, read the input, and whenever a visitor number \(s\) appears, set cnt[s] += 1.
   • Since the same number does not appear more than once on the same day, this correctly counts the “number of days.”
3. Among \(1 \le i \le N\), enumerate in ascending order those satisfying cnt[i] >= K and output them.
4. If no user satisfies the condition, output -1.

Complexity

• Time complexity: \(O\!\left(\sum_{j=1}^{D} M_j + N\right)\) (We add counts proportional to the total number of people appearing in the input, then check \(N\) people at the end)
• Space complexity: \(O(N)\) (Only the count array cnt)

Implementation Notes

• Since there can be days where \(M_j = 0\), it is safe to strictly follow the pattern of “read the number of people \(M\), then read exactly \(M\) numbers.”

• The output must be in ascending order, but checking the condition in order \(i=1..N\) naturally produces ascending order.

• Don’t forget the branch to output -1 only when the number of users satisfying the condition is 0.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    idx = 0
    N = data[idx]; D = data[idx+1]; K = data[idx+2]
    idx += 3

    cnt = [0] * (N + 1)
    for _ in range(D):
        M = data[idx]
        idx += 1
        for _ in range(M):
            s = data[idx]
            idx += 1
            cnt[s] += 1

    ans = [str(i) for i in range(1, N + 1) if cnt[i] >= K]
    if ans:
        print(" ".join(ans))
    else:
        print("-1")

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.