SEATING7 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

There are N seats, of which seats A_1, \ldots, A_M are already occupied.
K more people will enter, each person will occupy the lowest number seat that’s not occupied.
For each of these K people, find out which seat they will occupy.

EXPLANATION:

This problem can be solved by simply simulating the process correctly.

Store a boolean array B of length N, where B_i = 1 if the i-th seat is occupied and B_i = 0 otherwise.
Initially, set B_{A_1}, B_{A_2}, \ldots, B_{A_M} to 1, and everything else to 0.

Then, whenever a person enters,

  • Iterate i = 1, 2, 3, \ldots in order till you find the smallest i such that B_i = 0.
  • This person is going to sit in seat i.
    So, output i and then update B_i = 1.

A slightly faster solution than simulating every time, is to note that the answer is simply the first K unoccupied seats, i.e. the first K indices containing zeros in B.

TIME COMPLEXITY:

\mathcal{O}(NM) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    b = [0]*(n+1)
    for x in a: b[x] = 1
    
    ans = []
    for i in range(k):
        for j in range(1, n+1):
            if b[j] == 0:
                ans.append(j)
                b[j] = 1
                break
    print(*ans)