While coding the OJ judge system last year, Rar the Cat has encountered a problem with coding the judge queue and needs your help.
In this hypothetical scenario, there will be up to N submissions in total, each with a unique submission id (subID).
However, each submission should be in the queue with a different priority. Rar the Cat thus wants 4 ways to add a submission to the queue.
The 4 ways are:
Furthermore, there are also 4 ways for the judge to inspect or access the queue.
The 4 ways are:
In addition, the judge also needs to update the queue when a submission has been graded. There are 3 ways for the judge to update the queue:
It's now your job to implement all these functions!
Furthermore, an initialize function (void init(int X, int N) ) will also be called before any of the above functions are called. You can put any initialization code here.
This is a function call question, there is a template provided under Attachments. Please use that template, you do not need to declare int main() or input from file.
For testing purposes, you may uncomment the int main() from the template. Please remember to comment it back when submitting the problem.
Unless otherwise specified, 0 < N ≤ 1000000 for each testcase, this means that subID can range from 1 to N
X will be the maximum number of function calls for each testcase. The limits of X will be addressed in the subtask section.
It is guaranteed that the system will not attempt to add any submissions that are already in the queue into the queue again. However, a submission can be requeued after it has been deleted from the queue previously.
Subtask 1 (33%): X ≤ 10,000,000, There will only be the following functions: queue_front, push_back, pop_front
Subtask 2 (31%): X ≤ 10,000,000 There will not be the following functions: insert_before, insert_after, erase.
Subtask 3 (36%): X ≤ 10,000,000
Subtask 4 (0%): Sample Testcase
The first line of input (for your grader) will consist of 2 integers, X followed by N, where N is the maximum of all the subIDs in the problem.
12 5 push_back 1 push_back 2 push_front 3 sub_before 1 sub_after 1 insert_after 4 1 insert_before 5 4 pop_front pop_back erase 4 queue_front queue_back
3 2 1 5