[Solution] Cinema Ticketing Queue solution codechef

Cinema Ticketing Queue solution codechef


There are NN people, numbered from 11 to NN. They go to a cinema hall. Each of them buys a ticket, which has a number written on it. The number on the ticket of the ithith person is AiAi.

There are infinite seats in the cinema hall. The seats are numbered sequentially starting from 11. All the NN people stand in a queue to get their respective seats. Person 11 stands at the front of the queue, Person 22 stands in the second position of the queue, so on up to Person NN who stands at the rear of the queue. They were given seats in this manner:

Let the number on the ticket of the person currently standing in front of the queue be XX. If the XthXth seat is empty, the person gets out of the queue and takes the XthXth seat. Otherwise the person goes to the rear of the queue, and the number on his ticket is incremented by one – that is, it becomes X+1X+1.

Print the seat number occupied by each of the NN people.

Input Format

  • The first line of input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN.
  • The second line of each testcase line contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.

Output Format Cinema Ticketing Queue solution codechef

For each test case, print a single line containing NN space-separated integers, where the ithith integer denotes the seat number finally occupied by the Person ii.

Constraints Cinema Ticketing Queue solution codechef

  • 1T1041≤T≤104
  • 1N1051≤N≤105
  • 1AiN1≤Ai≤N
  • The sum of NN over all test cases does not exceed 51055⋅105.

Sample Input 1  Cinema Ticketing Queue solution codechef

4
5
1 2 3 2 4
4
4 1 3 2
3
1 1 1
5
2 5 1 5 2

Sample Output 1 

1 2 3 5 4
4 1 3 2
1 2 3
2 5 1 6 3 

Explanation

Test case 11:

  • First, the first, second, third, and fifth person get the seats numbered 112233, and 44 respectively because when they come to the front of the queue the corresponding seats are empty. The fourth person does not get the seat numbered 22, because when he comes to the front of the queue, the seat is already occupied by the second person. Hence he goes to the rear of the queue and the number on the ticket of the fourth person is incremented by one and becomes 33.
  • The fourth person does not get the seat numbered 33 because it is already occupied by the third person. Hence the number on the ticket of the fourth person is incremented by one and becomes 44.
  • Again, the fourth person does not get the seat numbered 44 because it is occupied by the fifth person. Hence the number on the ticket of the fourth person is incremented by one and becomes 55.
  • Finally the fourth person gets the seat numbered 55.

Test case 33:

  • The first person gets the seat numbered 11. The second and third people do not get the seat numbered 11 because when they come to the front of the queue, the seat is already occupied by the first person. Hence the number on the tickets of both is incremented by one and becomes 22.

  • Then, the second person gets the seat numbered 22. The third person does not get the seat numbered 22 because when he comes to the front of the queue, it is already occupied by the second person. Hence the number on the ticket of the third person is increased to 33.

  • Finally, the third person gets the seat numbered 33.

Solution: Click here

 

Leave a Comment