P2278 [HNOI2003] Operating System

Write a program to simulate process scheduling in an operating system. Assume the system has only one CPU. For each process, its arrival time, execution time, and priority are known. The priority is represented by natural numbers; a larger number means a higher priority. If a process arrives when the CPU is idle, it will occupy the CPU continuously until it finishes, unless during this time a process with a higher priority needs to run. In that case, the new (higher-priority) process will take the CPU, and the old one must wait. If a process arrives while the CPU is executing a process with a higher or equal priority, then the newly arrived process must wait. Once the CPU becomes idle, if there are processes waiting, choose the one with the highest priority to run first. If there are multiple processes with the highest priority, choose the one with the earliest arrival time.

The input contains several lines. Each line has four natural numbers (each not exceeding $10^8$): process ID, arrival time, execution time, and priority. Different processes have different IDs. No two processes with the same priority arrive at the same time. The input is sorted in non-decreasing order of arrival time. It is guaranteed that at any time, the number of processes in the waiting queue does not exceed 15000.

Output the process ID and its completion time for each process, in the order of their completion times.

Translated by ChatGPT 5