10167. Student’s queue in a canteen

 

In ADA University students like Programming competitions very much, so each student belongs to one (and only one) team. But the rules of different competitions are different, and not usually one team consists of 3 members like according to ACM rules. Any team can contain any number of students (but of course more than 0).

Students like to come to their canteen which is a building C and spent their free time with a cup of coffee. Students in ADA are very smart, they do not want to stand in standard queue for delicious coffee. They decided to establish some rules that only they would follow.

If a student enters the queue, he first searches the queue from head to tail to check if some of his teammates (student of the same team) are already in the queue. If yes, he enters the queue right behind them (behind all his teammates). If not, he enters the queue at the tail and becomes the new last element (bad luck). Dequeuing is done like in normal queues: students are processed from head to tail in the order they appear in the queue.

Your task is to write a program that simulates such a queue.

 

Input. First line contains number of teams t (1 ≤ t ≤ 1000). Each of the next t lines describes one team. First element in the line is the number n (1 ≤ n ≤ 1000) of students in a team. Next n integers in a line give the ID's (0 ≤ ID ≤ 106) of students in a team.

Finally, a list of commands follows. There are two different kinds of commands:

·        ENQUEUE x – student x enters into the queue

·        DEQUEUE – process the first student and remove him from the queue

 

Output. For each DEQUEUE command print the element which is dequeued on a single line.

 

Sample input 1

Sample output 1

2

3 1 2 3

3 4 5 6

ENQUEUE 1

ENQUEUE 4

ENQUEUE 2

ENQUEUE 5

ENQUEUE 6

ENQUEUE 3

DEQUEUE

DEQUEUE

DEQUEUE

DEQUEUE

DEQUEUE

DEQUEUE

1

2

3

4

5

6

 

 

Sample input 2

Sample output 2

2

3 1 2 3

3 4 5 6

ENQUEUE 1

ENQUEUE 4

ENQUEUE 2

DEQUEUE

DEQUEUE

ENQUEUE 5

ENQUEUE 3

ENQUEUE 6

DEQUEUE

DEQUEUE

DEQUEUE

DEQUEUE

1

2

4

5

6

3

 

Sample input 3

Sample output 3

3

3 11 12 13

3 24 25 26

3 47 48 49

ENQUEUE 11

ENQUEUE 47

ENQUEUE 48

ENQUEUE 12

ENQUEUE 24

ENQUEUE 49

DEQUEUE

DEQUEUE

DEQUEUE

ENQUEUE 13

DEQUEUE

DEQUEUE

DEQUEUE

11

12

47

48

49

24

 

 

SOLUTION

queue

 

Algorithm analysis

For each student, remember the number of the team to which he belongs. Let teamBelongTo[ID] contains the number of the team to which the student with ID (ID ≤ 106) belongs.

int teamBelongTo[1000001];

 

Declare an array of queues teamQueue.

queue<int> teamQueue[1001];

Each queue includes only members of one team. There are no more than 1000 teams. The teams will be numbered from 0.

 

Students will always queue up in groups (teams). Let's declare a general queue combinedQueue that contains the team numbers of the groups of students in the queue.

queue<int> combinedQueue;

 

Consider the execution of the command ENQUEUE n. Let's determine the team, which student n belongs to. If there is no a single student from the team in the queue, then student n goes to the end of the general queue. The members of the team move to the end of the combinedQueue. Add student n to the end of the teamQueue[team] queue.

 

Consider the execution of the command DEQUEUE. The head of combinedQueue contains the team number of the first student in the queue. Remove the student from the queue. If it was the last student from the team (teamQueue[team] becomes empty), then remove the head of the combinedQueue queue.

 

Example

Consider the third test case. There are three teams. Array teamBelongTo has the form:

- team 0 consists of students 11, 12, 13;

- team 1 consists of students 24, 25, 26;

- team 2 consists of students 47, 48, 49;

 

Let's simulate the first 5 commands (they all have the ENQUEUE type). The general queue has a form (above, next to each student ID, his team number is indicated):

Array of queues teamQueue has a form:

The combinedQueue is as follows:

It means that in the general queue, first there is a group of students from team 0, then a group from team 2 and at the end a group from team 1.

 

We receieved a command ENQUEUE 49. Compute which team belongs to the student with ID = 49: teamBelongTo[49] = 2. Check if there are representatives of the team number 2 in the general queue. To do this, check if the teamQueue[2] is empty. No, it is not empty, therefore nothing needs to be done with the combinedQueue. Student with ID = 49 will be added to the end of the teamQueue[2] queue, now teamQueue[2] = {47, 48, 49}.

Array of queues teamQueue is as follows:

 

Next given three commands DEQUEUE. When executing first two commands, students with numbers 11 and 12 are removed from the queue. As soon as teamQueue[0] becomes empty, team number 0 should be removed from the head of combinedQueue. The third student with ID = 47 will leave the queue.

The state of the queues takes thee form:

Array of queues teamQueue is as follows:

 

The next command is ENQUEUE 13. Student with ID = 13 belongs to the team number teamBelongTo[13] = 0. There are no representatives of team number 0 in the queue (teamQueue[0] is empty). Therefore, team number 0 should be placed at the end of the combinedQueue. Update teamQueue[0] = {13}.

Array of queues teamQueue is as follows:

 

Algorithm realization

For each student, memoize the number of the team which he belongs to. Let teamBelongTo[ID] contains the number of the team which the student ID belongs to.

 

int teamBelongTo[1000001];

 

Declare an array of queues teamQueue. Each queue includes only members of one team. There are no more than 1000 teams.

 

queue<int> teamQueue[1001];

 

Read the number of teams numTeams. The teams will be numbered from 0.

 

cin >> numTeams;

for (t = 0; t < numTeams; t++)

{

 

Clear the queue of the team number t.

 

  while (!teamQueue[t].empty()) teamQueue[t].pop();

 

Read the data of the team number t. Team number t contains numElem members.

 

  cin >> numElem;

  while (numElem--)

  {

    cin >> elem;

 

The participant number elem belongs to thr team number t.

 

    teamBelongTo[elem] = t;

  }

}

 

Declare a general queue combinedQueue that contains the team numbers of the groups of students in the queue.

 

queue<int> combinedQueue;

 

Process the commands till the end of file.

 

while (cin >> command)

{

 

Student number num came. Insertion to the queue.

 

  if (command[0] == 'E')

  {

    cin >> num;

 

Student number num belongs to team team.

 

    team = teamBelongTo[num];

 

If there is no a single student from the team in the queue, then student num goes to the end of the general queue. The members of the team move to the end of the combinedQueue.

 

    if (teamQueue[team].empty()) combinedQueue.push(team);

 

Add student num to the end of the teamQueue[team] queue.

 

    teamQueue[team].push(num);

  }

  else

  {

 

The head of combinedQueue contains the team number of the first student in the queue. Remove the student from the queue. If it was the last student from the team (teamQueue[team] becomes empty), then remove the head of the combinedQueue queue.

 

    team = combinedQueue.front();

    cout << teamQueue[team].front() << '\n';

    teamQueue[team].pop();

    if (teamQueue[team].empty()) combinedQueue.pop();

  }

}