1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
# python3
from collections import namedtuple, deque
Request = namedtuple("Request", ["arrived_at", "time_to_process"])
Response = namedtuple("Response", ["was_dropped", "started_at"])
class Buffer:
def __init__(self, capacity):
self.capacity = capacity
self.finish_time = deque()
self.running_time_counter = 0
def process(self, request):
if self.running_time_counter < request.arrived_at:
if len(self.finish_time) == 0:
self.running_time_counter = request.arrived_at
elif self.finish_time[-1] < request.arrived_at:
self.running_time_counter = request.arrived_at
while len(self.finish_time) > 0:
j = self.finish_time[0]
if j <= request.arrived_at:
self.finish_time.popleft()
else:
break
if len(self.finish_time) >= self.capacity:
return Response(True, -1)
response = Response(False, self.running_time_counter)
self.running_time_counter = self.running_time_counter + request.time_to_process
if len(self.finish_time) > 0:
self.finish_time.append(self.finish_time[-1] + request.time_to_process)
else:
self.finish_time.append(self.running_time_counter)
return response
def process_requests(requests, buffer):
responses = []
for request in requests:
responses.append(buffer.process(request))
return responses
def main():
buffer_size, n_requests = map(int, input().split())
requests = []
for _ in range(n_requests):
arrived_at, time_to_process = map(int, input().split())
requests.append(Request(arrived_at, time_to_process))
buffer = Buffer(buffer_size)
responses = process_requests(requests, buffer)
for response in responses:
print(response.started_at if not response.was_dropped else -1)
if __name__ == "__main__":
main()
|
