Untitled
unknown
plain_text
a year ago
11 kB
10
Indexable
Never
[Problem Description]
There are L number of production lines and M pieces of different equipment that are shared to be used for the production lines.
A production request is made to each line. Given the product ID to be produced, equipment to be used for production, and production time.
Each line processes requests in order of time they are made. Since one equipment can only be used for one production line at a time, the other lines must wait until the line finishes its production.
If there are several production lines that need the equipment when the line finishes the production, they are assigned the equipment in ascending of their line numbers.
Each production line operates following the below process:
A new production request is made to an idle production line (Required Equipment E, Required Time T) at Time X,
If there is any waiting production request, the new request is added to the end of the waiting queue.
If there is no waiting production request and E is available, the production line starts production at X.
If there is no waiting production request, but E is not available, the production line will be waiting.
The production line, which starts production at X, finishes it at X+T. If there is a waiting request at X+T, the line tries producing at X+T. In this case, any request made at X+T is also included. The availability of the equipment required for production determines whether the line starts production at X+T or not; it might have to stop and wait.
When E becomes available at X+T, it is assigned to the line with the smallest line number among the ones that need the equipment. In this case, any request made at X+T is also included. E can also be assigned again at X+T to the production line that has just finished using it. A production line assigned E starts production at X+T.
Write a program that processes the production request and checks the product status in every particular times.
Implement each required function by referring to the following API description.
※ The function signature below is based on C/C++. As for other languages, refer to the provided Main and User Code.
The following is the description of API to be written in the User Code
void init(int L, int M)
This is called in the beginning of each test case.
Time is 0 when this function is called.
Given L, the number of production lines, and M, the number of pieces of equipment.
L number of production lines are given a number from 0, 1, 2, … to L-1, and M from 0, 1, 2, … to M-1.
Parameters
L : Number of production lines (3 ≤ L ≤ 500)
M : Number of pieces of different equipment (3 ≤ M ≤ 500)
int request(int tStamp, int pId, int mLine, int eId, int mTime)
A production request for a product pId is made at tStamp to a production line mLine. The required equipment for production is eId and the required time is mTime.
For each test case, products have different “pId”s.
The ID of the product, which mLine is producing, is returned.
If there is no such product, -1 is returned.
If production starts at tStamp, the ID of the product for which the production starts needs to be returned.
If production finishes at tStamp and either there is no waiting request or the required equipment is not available, -1 needs to be returned.
Parameters
tStamp : Time when the production request is made ( 1 ≤ tStamp < 500,000 )
pId : Product ID ( 0 ≤ pId < 1,000,000,000 )
mLine : Line number to which the production request is made ( 0 ≤ mLine < L )
eId : Equipment number required for production ( 0 ≤ eId < M )
mTime : Time taken for production ( 1 ≤ mTime ≤ 2,000 )
Returns
-1 is returned if there is no product being produced; if not, the ID of the product being produced is returned.
int status(int tStamp, int pId)
This function checks the status of pId at tStamp.
If no production request is made, 0 is returned.
If it is waiting in the current production line, 1 is returned.
If it is being produced, 2 is returned; if the production is finished, 3 is returned.
Parameters
tStamp : Time to return the product status ( 1 ≤ tStamp < 500,000 )
pId : Product ID ( 0 ≤ pId < 1,000,000,000 )
Returns
At tStamp, the status of pId – 0, 1, 2, or 3 – is returned.
(0 – No request, 1 - Waiting, 2 – In production, 3 – Production finished)
[Example]
Think of the following case in [Table 1].
Order
Function
Return
Figure
1
init(3, 3)
2
request(1, 111, 0, 0, 5)
111
Fig. 1
3
request(2, 222, 2, 0, 3)
-1
Fig. 2
4
request(3, 333, 1, 0, 7)
-1
Fig. 3
5
request(4, 444, 0, 1, 20)
111
Fig. 4
6
status(5, 333)
1
7
request(6, 555, 0, 2, 15)
444
Fig. 5
8
status(8, 333)
2
9
request(10, 666, 1, 0, 6)
333
Fig. 6
10
status(13, 333)
3
11
request(14, 777, 1, 1, 12)
666
Fig. 7
12
request(16, 888, 1, 0, 5)
666
Fig. 8
13
status(19, 222)
2
Fig. 9
14
status(22, 222)
3
[Table 1]
(Order #1) Given 3, the number of production lines, and 3, the number of pieces of equipment. All production lines are empty in the initial status.
(Order #2) At 1, a production request for the product 111 is made to the production line 0. The equipment number required to produce 111 is 0 and the required production time is 5. Production starts using the equipment 0. The product ID, 111, is returned.
[Fig. 1] shows the results of the functions called.
[Fig. 1]
(Order #3) At 2, a production request for the product 222 is made to the production line 2. The equipment number required to produce 222 is 0 and the required production time is 3. Since the equipment is not available now, the production line needs to wait. Since there is no product being produced, -1 is returned.
[Fig. 2] shows the results of the function called.
[Fig. 2]
(Order #4) At 3, a production request for the product 333 is made to the production line 1. The equipment number required to produce 333 is 0 and the required production time is 7. Since the equipment is not available now, the production line needs to wait. Since there is no product being produced, -1 is returned.
[Fig. 3] shows the results of the function called.
[Fig. 3]
(Order #5) At 4, a production request for the product 444 is made to the production line 0. The equipment number required to produce 444 is 1 and the required production time is 20. Since the line 0 is not available now, the request is not processed. 111, the ID of the product being produced, is returned.
[Fig. 4] shows the results of the function called.
[Fig. 4]
(Order #6) At 5, the status of the product 333 is checked. Since 333 is waiting to be produced, 1 is returned.
(Order #7) At 6, a production request for the product 555 is made to the production line 0. The equipment number required to produce 555 is 2 and the required production time is 15. Since the line 0 is not available now, the request is not processed. 444, the ID of the product being produced, is returned.
[Fig. 5] shows the results of the functions called.
[Fig. 5]
(Order #8) At 8, the status of the product 333 is checked. Since 333 is being produced, 2 is returned.
(Order #9) At 10, a production request for the product 666 is made to the production line 1. The equipment number required to produce 666 is 0 and the required production time is 6. Since the line 1 is not available now, the request is not processed. 333, the ID of the product being produced, is returned.
[Fig. 6] shows the results of the functions called.
[Fig. 6]
(Order #10) At 13, the status of the product 333 is checked. Since producing 333 is finished, 3 is returned.
(Order #11) At 14, a production request for the product 777 is made to the production line 1. The equipment number required to produce 777 is 1 and the required production time is 12. Since the line 1 is not available now, the request is not processed. 666, the ID of the product being produced, is returned.
[Fig. 7] shows the results of the functions called.
[Fig. 7]
(Order #12) At 16, a production request for the product 888 is made to the production line 1. The equipment number required to produce 888 is 0 and the required production time is 5. Since the line 1 is not available now, the request is not processed. 666, the ID of the product being produced, is returned.
[Fig. 8] shows the results of the function called.
[Fig. 8]
(Order #13) At 19, the status of the product 222 is checked. 2 is returned since production for 222 starts after the equipment 0 is assigned at 19, as shown in [Fig. 9].
[Fig. 9]
(Order #14) At 22, the status of the product 222 is checked. Since producing 222 is finished, 3 is returned.
[Constraints]
1. init() is called in the beginning of each test case
2. For each test case, tStamp is a value that keeps increasing.
3. For each test case, the sum of calls of the all functions is less than or equal to 20,000.
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
extern void init(int L, int M);
extern int request(int tStamp, int pId, int mLine, int eId, int mTime);
extern int status(int tStamp, int pId);
/////////////////////////////////////////////////////////////////////////
#define CMD_INIT 1
#define CMD_REQUEST 2
#define CMD_STATUS 3
static bool run() {
int q;
scanf("%d", &q);
int l, m, tstamp, pid, mline, eid, mtime;
int cmd, ans, ret = 0;
bool okay = false;
for (int i = 0; i < q; ++i) {
scanf("%d", &cmd);
switch (cmd) {
case CMD_INIT:
scanf("%d %d", &l, &m);
init(l, m);
okay = true;
break;
case CMD_REQUEST:
scanf("%d %d %d %d %d %d", &tstamp, &pid, &mline, &eid, &mtime, &ans);
ret = request(tstamp, pid, mline, eid, mtime);
if (ans != ret)
okay = false;
break;
case CMD_STATUS:
scanf("%d %d %d", &tstamp, &pid, &ans);
ret = status(tstamp, pid);
if (ans != ret)
okay = false;
break;
default:
okay = false;
break;
}
}
return okay;
}
int main() {
setbuf(stdout, NULL);
//freopen("sample_input.txt", "r", stdin);
int T, MARK;
scanf("%d %d", &T, &MARK);
for (int tc = 1; tc <= T; tc++) {
int score = run() ? MARK : 0;
printf("#%d %d\n", tc, score);
}
return 0;
}
void init(int L, int M) {
return;
}
int request(int tStamp, int pId, int mLine, int eId, int mTime) {
return 0;
}
int status(int tStamp, int pId) {
return 0;
}
25 100
14
1 3 3
2 1 111 0 0 5 111
2 2 222 2 0 3 -1
2 3 333 1 0 7 -1
2 4 444 0 1 20 111
3 5 333 1
2 6 555 0 2 15 444
3 8 333 2
2 10 666 1 0 6 333
3 13 333 3
2 14 777 1 1 12 666
2 16 888 1 0 5 666
3 19 222 2
3 22 222 3