Editorial for Service Desk
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Approach
We simulate the process directly in chronological order.
Key requirements:
- Odd second: serve earliest-arrived waiting customer.
- Even second: serve earliest-arrived urgent customer if one exists, otherwise earliest-arrived normal customer.
- Arrival times are all distinct.
Use three queues:
all_q: all waiting customers by arrival order.urgent_q: waiting urgent customers by arrival order.normal_q: waiting normal customers by arrival order.
When a customer is served from one queue, they may still appear in the others, so we keep a
served[] array and lazily discard already-served indices from queue fronts.
To avoid iterating over huge idle gaps, if no one is waiting and the next customer arrives later, we jump current time directly to that next arrival second.
Time complexity is because each customer is inserted once and removed once per queue with
amortized constant work.
Solution (Python)
from collections import deque
import sys
def main() -> None:
input = sys.stdin.readline
n = int(input())
customers: list[tuple[int, int, str]] = []
for idx in range(1, n + 1):
t_str, c = input().split()
customers.append((int(t_str), idx, c))
customers.sort(key=lambda x: (x[0], x[1]))
all_q: deque[tuple[int, str]] = deque()
urgent_q: deque[int] = deque()
normal_q: deque[int] = deque()
served = [False] * (n + 1)
answer: list[str] = []
i = 0
served_count = 0
waiting_count = 0
current_time = 1
while served_count < n:
while all_q and served[all_q[0][0]]:
all_q.popleft()
if waiting_count == 0 and i < n and current_time < customers[i][0]:
current_time = customers[i][0]
while i < n and customers[i][0] <= current_time:
_, idx, kind = customers[i]
all_q.append((idx, kind))
if kind == "U":
urgent_q.append(idx)
else:
normal_q.append(idx)
waiting_count += 1
i += 1
if waiting_count > 0:
if current_time % 2 == 1:
while served[all_q[0][0]]:
all_q.popleft()
idx, _ = all_q.popleft()
else:
while urgent_q and served[urgent_q[0]]:
urgent_q.popleft()
while normal_q and served[normal_q[0]]:
normal_q.popleft()
if urgent_q:
idx = urgent_q.popleft()
else:
idx = normal_q.popleft()
served[idx] = True
answer.append(str(idx))
served_count += 1
waiting_count -= 1
current_time += 1
sys.stdout.write("\n".join(answer) + "\n")
if __name__ == "__main__":
main()
Comments