50162. RPG Queue

I'm a slow walker, but I never walk backwards.

Task Description

We are writing a queuing system for an RPG. There are three classes in the game: damage per second (DPS), healer, and tank. Players must form 5-person party to enter a dungeon. A party has one tank, one healer and three DPS's.

Every player has a non-negative player id. If the player id is $3n$, then the player is a DPS. If the player id is $3n + 1$, then the player is a healer. If the player id is $3n + 2$, then the player is a tank.

Each class of players form a queue to enter the dungeon. The players enter the dungeon in a first-come-first-serve manner. When we have three DPS's, one healer, and one tank in the queues, those at the head of the queues form a party and enter the dungeon. Those not in the head of the queues will wait. Write a program to arrange parties and output player ids in the same party. Please refer to the following animation.

samplesample

We assume that the number of waiting player of every class is no more than 5000. That means the maximum size of each queue is 5000. If the total size of the three queues exceeds 15,000, you will get an MLE. Please use the technique in the hint to solve the memory problem. Also using the linked list to solve this problem is not allowed and will get a CE.

Hint

Since the number of waiting players is no more than 5000, we can reuse the array in a circular manner. Also note that % is very useful in this case.

samplesample

Input Format

The input has a sequence of non-negative player ids indicating the incoming players in order, and you should process all of them until EOF.

Output Format

The output consists of lines, and each line has five player ids for a party. The lines are in the order of the parties are formed. The first three ids are DPS, in the order they queued, then the healer, and then the tank.

Subtask

  • 50 points: The total number of players from each class does not exceed 5000.
  • 50 points: The number of waiting players in each queue does not exceed 5000. You need to use the techniques in the hint to solve the memory problem.

Sample Input 1

6 8 21 33 14 57 63 9 10 77 5 61 7 30 42 3 1

Sample Output 1

6 21 33 10 8
57 63 9 61 14
30 42 3 7 77

Sample Input 2

Sample Inupt 2

Sample Output 2

Sample Output 2

Discussion