کافه‌ سالاد

Main.py

import heapq

expHeap = [] # heap of [ expiration date, client id ]
stringHeap = [] # heap of [ string, client id ]

MAX_K = 100010
mark = [0] * MAX_K # if client with ID has been exipred mark[ID] = True
string = [0] * MAX_K # string of each client
lastClientId = 0 # number of clients

n = int(input())

for currentDay in range(n):
    clients = list(map(str, input().split()))
    for i in range(1, len(clients), 2):
        heapq.heappush(stringHeap, [clients[i], lastClientId])
        heapq.heappush(expHeap, [int(clients[i+1]) + currentDay - 1, lastClientId])
        string[lastClientId] = clients[i]
        lastClientId += 1
    # erase all clients that has been expired
    result = [] # list of exipred people
    while True:
        if len(expHeap) == 0:
            break
        minElement = heapq.heappop(expHeap)
        id = minElement[1]
        if minElement[0] <= currentDay: # expired
            if mark[ id ] == False: # if == True means we delete him earlier
                result.append(string[ id ])
            mark[ id ] = True
        else : # all exp dates are greater than current day
            heapq.heappush(expHeap, minElement)
            break
    # erase single client with smalles string
    while True:
        if len(stringHeap) == 0:
            break
        minElement = heapq.heappop(stringHeap)
        id = minElement[1]
        if mark[id] == False:
            mark[id] = True
            result.append(string[id])
            break

    result.sort()
    for x in result:
        print(x, end = " ")
    print()