RTE '16 J2 - Guidance Counselling

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Java 8 1.4s
Python 2 1.8s
Python 3 1.8s
Memory limit: 64M

Author:
Problem type

At RHHS, the most you can do to ensure your timetable aligns with your course selections is to pray. Perhaps you'll have only one course this semester, or maybe even three spares? Maybe you'll get an alternate you didn't even think about choosing, or maybe you'll be forced to take vocal music?

As a result of these timetable catastrophes, a very long line has formed outside the guidance office, and they are unable to process them all. Each student in the line has a timetable change slip i, which has a color c_i and a number m_i (0 \le m_i \le 10^9) (which may not be unique, since guidance makes mistakes sometimes). The color of a timetable change slip corresponds with the following types of requests (listed in order of priority):

  1. BLUE - Drop course
    • A drop course request is the highest priority, since it gives more space in that class for other students to switch into.
  2. PINK - Urgent course change (no lunch period, five spares etc.)
  3. GREEN - Preferential course change (wait no I don't want to take AP chemistry anymore)

The timetable change slips are not processed in the order they are given out – instead they are processed in the order of their color (i.e. all blue slips are processed first, then pink slips, then green slips). If multiple people have the same color slip, then the lowest numbered slip is processed first.

Your guidance counsellor has chosen you for the task of creating a program to manage the line, ensuring all students are processed in the correct order.

Input Specification

The first line contains an integer Q (1 \le Q \le 400\,000), which specifies the number of queries to make to your program. The next Q lines each contain a query. There are two types of queries, an ADD query and a NEXT query. An ADD query adds a new student with a timetable change slip into the line, and a NEXT query gets the next person in the line as defined by the order above.

An ADD query looks like this:

ADD ci mi

…which adds a student with a timetable change slip with color c_i and number m_i into the line.

A NEXT query looks like this:

NEXT

…which outputs c_i and m_i of the next slip to be processed.

For test cases worth 20 of 100 points, Q \le 1000.

Output Specification

For every NEXT query, print out c_i and m_i of the next student to be processed. If there is nobody to be processed, print out NONE.

Sample Input

6
ADD PINK 1
ADD BLUE 1
NEXT
ADD GREEN 1
ADD PINK 2
NEXT

Sample Output

BLUE 1
PINK 1

Explanation for Sample Output

The first two queries add pink slip #1 and blue slip #1 into the line. The next student to be processed is blue slip #1, because blue slips have precedence over pink. Students with green slip #1 and pink slip #2 are then added into the line. As of this moment, there are three students in the line: pink slip #1, pink slip #2, and green slip #1. Pink slips have precedence over green slips, so one of the two pink slips will be processed first. Since pink slip #1 has a lower number than pink slip #2, it is processed first.


Comments

There are no comments at the moment.