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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
#include <iostream>
#include <queue>
#include <vector>
//#include <gtest/gtest.h>
struct Request {
Request(int arrival_time, int process_time) :
arrival_time(arrival_time), process_time(process_time) {
}
int arrival_time;
int process_time;
};
struct Response {
Response(bool dropped, int start_time) :
dropped(dropped), start_time(start_time) {
}
bool dropped;
int start_time;
};
class Buffer {
public:
Buffer(int capacity) :
capacity_(capacity), finish_time_() {
}
Response Process(const Request &request) {
// write your code here
if (runningTimeCounter_ < request.arrival_time) {
if (finish_time_.size() == 0)
runningTimeCounter_ = request.arrival_time;
else if (finish_time_.back() < request.arrival_time)
runningTimeCounter_ = request.arrival_time;
}
while (finish_time_.size() > 0) {
int j = finish_time_.front();
if (j <= request.arrival_time)
finish_time_.pop();
else
break;
}
if (finish_time_.size() >= capacity_) {
return Response(true, -1);
}
Response response = Response(false, runningTimeCounter_);
runningTimeCounter_ = runningTimeCounter_ + request.process_time;
if (finish_time_.size() > 0)
finish_time_.push(finish_time_.back() + request.process_time);
else
finish_time_.push(runningTimeCounter_);
return response;
}
private:
size_t capacity_;
std::queue<int> finish_time_;
int runningTimeCounter_ = 0;
};
std::vector<Request> ReadRequests() {
std::vector<Request> requests;
int count;
std::cin >> count;
for (int i = 0; i < count; ++i) {
int arrival_time, process_time;
std::cin >> arrival_time >> process_time;
requests.push_back(Request(arrival_time, process_time));
}
return requests;
}
std::vector<Response> ProcessRequests(const std::vector<Request> &requests,
Buffer *buffer) {
std::vector<Response> responses;
for (size_t i = 0; i < requests.size(); ++i)
responses.push_back(buffer->Process(requests[i]));
return responses;
}
void PrintResponses(const std::vector<Response> &responses) {
for (size_t i = 0; i < responses.size(); ++i)
std::cout << (responses[i].dropped ? -1 : responses[i].start_time)
<< std::endl;
}
//TEST(ProcessRequests, t) {
// int bufferMaxSize = 1;
// Buffer buf = Buffer(bufferMaxSize);
// std::vector<Request> requests;
// std::vector<Response> responses = ProcessRequests(requests, &buf);
// ASSERT_EQ(0, responses.size());
//}
//
//TEST(ProcessRequests, t1) {
// int bufferMaxSize = 1;
// Buffer buf = Buffer(bufferMaxSize);
// std::vector<Request> requests = {Request(0, 1)};
// std::vector<Response> responses = ProcessRequests(requests, &buf);
// ASSERT_EQ(1, responses.size());
// ASSERT_EQ(false, responses[0].dropped);
//}
//
//TEST(ProcessRequests, t2) {
// int bufferMaxSize = 1;
// Buffer buf = Buffer(bufferMaxSize);
// std::vector<Request> requests = {Request(0, 1), Request(0, 1)};
// std::vector<Response> responses = ProcessRequests(requests, &buf);
// ASSERT_EQ(2, responses.size());
// ASSERT_EQ(false, responses[0].dropped);
// ASSERT_EQ(0, responses[0].start_time);
// ASSERT_EQ(true, responses[1].dropped);
//}
//
//TEST(ProcessRequests, t3) {
// int bufferMaxSize = 1;
// Buffer buf = Buffer(bufferMaxSize);
// std::vector<Request> requests = {Request(0, 1), Request(1, 1)};
// std::vector<Response> responses = ProcessRequests(requests, &buf);
// ASSERT_EQ(2, responses.size());
// ASSERT_EQ(false, responses[0].dropped);
// ASSERT_EQ(0, responses[0].start_time);
// ASSERT_EQ(false, responses[1].dropped);
// ASSERT_EQ(1, responses[1].start_time);
//}
int main() {
int size;
std::cin >> size;
std::vector<Request> requests = ReadRequests();
Buffer buffer(size);
std::vector<Response> responses = ProcessRequests(requests, &buffer);
PrintResponses(responses);
return 0;
}
|
