AFW2319
unknown
plain_text
a year ago
14 kB
4
Indexable
[Problem Description]
You are given information about when employees arrive at and leave work.
You are required to decide when to start an announcement in order for M or more employees to hear the announcement at the office.
[Fig. 1] shows the clock-in and -out times of five employees. Employee 1’s clock-in and -out times are 0 and 4 seconds, respectively.
Employee 2’s clock-in and -out times are 3 and 13 seconds, respectively.
If the announcement lasts for 2 seconds and 2 or more people must hear it, the earliest time to start the announcement is 3 seconds.
If the announcement lasts for 2 seconds and 3 or more people must hear it, the earliest time to start the announcement is 8 seconds.
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()
This function is called in the beginning of each test case.
Employees’ clock-in and -out times are not registered.
int add(int mId, int mStart, int mEnd)
{
The times an employee with the ID of mId arrives at work mStart and leaves work mEnd are added.
Each time is given in the unit of seconds.
If the ID exists already, make changes to the existing clock-in and -out times rather than adding them.
A deleted employee may be added again.
Parameters
mId: the employee ID ( 1 ≤ mId ≤ 1,000,000,000 )
mStart: the clock-in time ( 0 ≤ mStart < 85,400 )
mEnd: the clock-out time ( mStart < mEnd < 86,400 )
Returns
Return the number of employees whose clock-in and -out times are registered.}
int remove(int mId)
{Delete the clock-in and -out times of the employee with the ID of mId.
The ID of an employee who was deleted may be given.
Parameters
mId: the employee ID ( 1 ≤ mId ≤ 1,000,000,000 )
Returns
Return the number of employees whose clock-in and -out times are registered.}
int announce(int mDuration, int M)
{The duration of the announcement is mDuration, and M, which is the minimum number of employees to hear the announcement, is given.
Return the earliest time for an announcement to be heard by M or more people.
Return -1 if such time to begin the announcement does not exist.
Parameters
mDuration: the duration of the announcement ( 2 ≤ mDuration ≤ 3,600 )
M: the minimum number of employees to hear the announcement ( 2 ≤ M ≤ 2,500 )
Returns
Return the earliest announcement time, if M or more employees can hear the announcement
If not, return -1.}
Oder Function return
1 init()
2 add(1, 0, 4) 1
3 add(2, 3, 13) 2
4 add(3, 4, 10) 3
5 add(4, 11, 23) 4
6 add(5, 8, 18) 5 Fig. 1
7 announce(2, 2) 3
8 announce(2, 3) 8
9 announce(3, 3) 8
10 remove(3) 4 Fig. 2
11 announce(3, 3) 11
(Order 1) No employees are registered in the beginning.
(Order 2) An employee with the ID of 1, and the clock-in and -out times of 0 and 4 seconds is added.
Return 1 as the total number of registered employees.
(Order 3) An employee with the ID of 2, and the clock-in and -out times of 3 and 13 seconds is added.
Return 2 as the total number of registered employees.
(Order 4) An employee with the ID of 3, and the clock-in and -out times of 4 and 10 seconds is added.
Return 3 as the total number of registered employees.
(Order 5) An employee with the ID of 4, and the clock-in and -out times of 11 and 23 seconds is added.
Return 4 as the total number of registered employees.
(Order 6) An employee with the ID of 5, and the clock-in and -out times of 8 and 18 seconds is added.
Return 5 as the total number of registered employees. [Fig. 1] shows the result after calling the function.
(Order 7) The duration of the announcement is 2 seconds, and 2 or more employees must hear the announcement.
The earliest time for the announcement to begin is 3 seconds.
(Order 8) The duration of the announcement is 2 seconds, and 3 or more employees must hear the announcement.
The earliest time for the announcement to begin is 8 seconds.
(Order 9) The duration of the announcement is 3 seconds, and 3 or more employees must hear the announcement.
The earliest time for the announcement to begin is 8 seconds.
(Order 10) Delete the employee with the ID of 3. [Fig. 2] shows the result after calling the function.
Order 11) The duration of the announcement is 3 seconds, and 3 or more employees must hear the announcement.
The earliest time for the announcement to begin is 11 seconds.
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
extern void init();
extern int add(int mId, int mStart, int mEnd);
extern int remove(int mId);
extern int announce(int mDuration, int M);
/////////////////////////////////////////////////////////////////////////
#define CMD_INIT 1
#define CMD_ADD 2
#define CMD_REMOVE 3
#define CMD_ANNOUNCE 4
static bool run() {
int q;
scanf("%d", &q);
int mid, mstart, mend, mduration, m;
int cmd, ans, ret = 0;
bool okay = false;
for (int i = 0; i < q; ++i) {
scanf("%d", &cmd);
switch (cmd) {
case CMD_INIT:
init();
okay = true;
break;
case CMD_ADD:
scanf("%d %d %d %d", &mid, &mstart, &mend, &ans);
ret = add(mid, mstart, mend);
if (ans != ret)
okay = false;
break;
case CMD_REMOVE:
scanf("%d %d", &mid, &ans);
ret = remove(mid);
if (ans != ret)
okay = false;
break;
case CMD_ANNOUNCE:
scanf("%d %d %d", &mduration, &m, &ans);
ret = announce(mduration, m);
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() {
return;
}
int add(int mId, int mStart, int mEnd) {
return 0;
}
int remove(int mId) {
return 0;
}
int announce(int mDuration, int M) {
return 0;
}
25 100
11
1
2 1 0 4 1
2 2 3 13 2
2 3 4 10 3
2 4 11 23 4
2 5 8 18 5
4 2 2 3
4 2 3 8
4 3 3 8
3 3 4
4 3 3 11
100
1
2 3799193 53006 64373 1
2 639546083 16710 30167 2
2 1588076 68528 76380 3
2 8911646 10553 75910 4
2 2166108 79475 79756 5
2 7716110 29729 32822 6
2 2280509 21619 31241 7
2 3133287 3482 42827 8
2 9199098 55828 63090 9
2 5690376 83879 84232 10
2 2263386 57861 65362 11
2 5961189 58423 68881 12
2 8391792 61418 78416 13
2 563713 64445 72637 14
2 4239627 29886 31199 15
2 5450211 19840 49495 16
2 8160571 47720 67919 17
2 6536851 64632 66503 18
2 8444800 82376 83488 19
2 4960631 35061 44955 20
2 5585359 69116 86035 21
3 2280509 20
2 96323477 47458 68609 21
2 4517600 68106 80128 22
2 2447557 47429 77041 23
2 7766447 51106 79091 24
2 8876770 46036 65722 25
2 912356 50247 63220 26
3 2280509 26
2 2287812 81999 84180 27
2 6077366 42977 71358 28
2 7127941 19307 55601 29
2 4401263 10050 13491 30
2 9192201 2932 75685 31
2 7621587 7686 53639 32
2 4007245 18064 35033 33
2 274935 44994 81947 34
4 2987 8 19840
2 4364402 78707 79626 35
2 4430001 74023 86189 36
2 8270622 76014 81030 37
2 2732669 85003 86345 38
2 9933863 36794 81803 39
4 3175 3 7686
2 6766048 29739 61952 40
3 3799193 39
3 2287812 38
2 3637328 40249 54832 39
2 511932423 5565 39531 40
2 713547 82468 83871 41
2 1326230 81000 81182 42
2 1915256 25435 51000 43
2 8218186 3365 55554 44
2 830923113 42695 71045 45
3 2732669 44
2 3281153 24604 41405 45
2 2998553 54038 78837 46
2 6473571 43030 80983 47
2 652539357 32784 40361 48
2 49051208 59562 62664 49
2 2394522 17141 33426 50
3 96323477 49
2 9480530 20725 74602 50
2 2117009 73511 84749 51
4 2031 5 7686
2 7466471 36045 77515 52
2 8048065 1468 62845 53
4 1875 5 5565
3 5961189 52
2 548632 59315 83544 53
2 694679274 13581 79010 54
3 9933863 53
2 2140706 75541 81530 54
2 4517600 7655 64180 54
2 3361814 64457 66974 55
2 4545912 37843 58168 56
3 8218186 55
3 5690376 54
2 482438 25209 27470 55
2 29886 61403 81062 56
2 3677357 22755 46009 57
2 5555975 73418 86251 58
2 9192201 11372 40989 58
2 4971243 20902 44095 59
2 9275460 71808 80212 60
2 5477814 74505 80318 61
2 2732669 74923 83490 62
4 3239 5 7686
2 7697735 6562 69931 63
2 25614881 61516 61789 64
2 3996843 19086 47359 65
2 54304590 46184 47094 66
3 3677357 65
3 4364402 64
2 9686146 73359 74074 65
3 2280509 65
2 196354403 72469 76119 66
2 5258726 35888 57518 67
2 9199098 427 31688 67
200
1
2 2839194 29493 40978 1
2 147932 40823 43788 2
2 4609475 84921 85687 3
2 8483014 34984 47758 4
2 9467221 23635 62401 5
2 7150112 38370 52800 6
2 3412146 33549 69834 7
2 9164596 19127 38148 8
2 8846075 64049 80527 9
2 2898613 12424 85793 10
2 1624397 69490 70233 11
2 9635319 28146 36763 12
3 9467221 11
2 5015759 2930 21011 12
3 9164596 11
2 1680295 43530 52619 12
2 8880513 59156 68669 13
2 8519282 59078 72586 14
3 9164596 14
2 565770598 63965 72750 15
2 1758903 76139 85979 16
2 4702735 20692 83155 17
2 6239657 60828 72517 18
2 437235 40150 41127 19
2 430488 80328 81752 20
2 6110191 53437 65331 21
2 7695775 83660 85027 22
2 1837241 29636 68757 23
3 565770598 22
2 7944271 52244 55443 23
2 981212259 74924 81623 24
2 5405238 85184 85438 25
2 1056280 43643 46168 26
3 1837241 25
4 1644 3 28146
4 102 2 12424
2 1036578 53549 69754 26
3 1036578 25
2 354441818 20101 70354 26
3 8880513 25
2 4502757 59277 59665 26
2 8141263 15738 79251 27
2 7543286 84716 85758 28
2 6695749 83699 85489 29
3 981212259 28
2 4032861 31912 71465 29
2 8767367 46578 64491 30
3 2839194 29
2 4027326 83066 84134 30
2 2574588 58195 79020 31
2 1386211 39945 83543 32
2 317728989 9488 21673 33
2 6035859 83026 85959 34
2 29780828 43832 56716 35
2 76174 64913 78902 36
3 6239657 35
3 7944271 34
2 2966860 8927 46012 35
2 85049971 41169 70951 36
3 1056280 35
4 2571 3 9488
2 2370994 3941 13130 36
2 6379207 77831 82859 37
2 3261658 58716 83794 38
3 437235 37
2 5042551 79541 85275 38
2 6433489 1076 32717 39
3 430488 38
2 687977 69228 83461 39
3 4609475 38
2 975867077 68652 83185 39
3 687977 38
2 2662035 72384 83911 39
2 3912589 1080 23577 40
2 5046711 15274 18011 41
2 3154193 37748 56589 42
2 9530395 44918 49199 43
2 8003326 30560 30694 44
2 9101110 61179 79550 45
2 8784931 77395 79127 46
3 1680295 45
2 970491 47118 71439 46
2 3000117 4864 50977 47
2 6992031 30522 48803 48
2 90975096 73204 83000 49
2 4621519 38541 43027 50
3 975867077 49
2 4759719 19434 34699 50
3 8784931 49
2 4365055 67538 80131 50
3 975867077 50
2 8438103 63746 66427 51
2 7382321 25692 35757 52
2 8068972 17262 69980 53
2 4754462 21801 39302 54
2 3882253 25435 66201 55
4 2480 9 17262
2 466061780 35249 79780 56
2 6035859 52753 66251 56
2 2393537 57300 63613 57
2 8915027 83406 84999 58
2 7559245 28672 37593 59
2 8352503 8282 79003 60
2 767434 20860 27650 61
2 8394636 2191 11388 62
3 7543286 61
2 7251076 11343 76308 62
2 9716460 78633 82012 63
2 4032861 78289 83759 63
2 1448819 58400 77735 64
2 6402925 27248 61433 65
2 3312023 26242 48187 66
2 400321265 42932 69101 67
2 2591404 75190 80796 68
2 466061780 35745 63558 68
2 4759719 72083 85534 68
2 4561656 35555 43192 69
2 2952266 1349 56962 70
4 1941 10 12424
2 768551 794 67083 71
2 1851147 75268 75743 72
2 3875171 81376 85847 73
2 2133478 42800 45102 74
2 8069320 41371 75720 75
2 9382682 18717 51346 76
2 339199993 42839 67285 77
2 681025041 22806 56845 78
2 7710018 79598 83994 79
2 7559620 16975 36180 80
2 9031222 16681 30910 81
2 7952408 5427 6104 82
2 4987370 24133 57122 83
2 5588780 66167 81052 84
2 4181854 56081 77510 85
2 6445056 12667 73504 86
3 6402925 85
2 832059185 82955 84013 86
2 592158 68006 82950 87
2 1655531 80163 85823 88
2 8988837 17368 81105 89
2 3124144 43274 47504 90
2 2486637 68893 76665 91
2 3204503 16890 18619 92
2 244465 21836 33261 93
2 867835 726 76943 94
3 681025041 93
3 7251076 92
2 6605786 33516 41170 93
2 9031416 50191 68280 94
2 598928458 24301 35970 95
2 5097228 1727 49532 96
2 6534590 34881 42150 97
3 7559245 96
2 2572406 1537 11518 97
2 5920687 83075 84083 98
2 1906633 48252 56293 99
2 1290650 52638 75794 100
2 7533522 67831 83818 101
3 687977 101
3 4027326 100
2 3533360 4795 76560 101
2 5745090 6293 35098 102
3 867835 101
2 418402682 57645 72818 102
2 4569020 33639 62188 103
3 5042551 102
2 1122064 46919 83056 103
2 5280583 47181 67883 104
2 2774943 61908 80419 105
3 9635319 104
2 3784468 60362 66404 105
2 1365510 4113 42830 106
2 8250088 56035 83176 107
3 85049971 106
3 8915027 105
2 1262326 6289 28286 106
4 772 35 60362
2 6503601 77350 85933 107
2 5745090 43158 78031 107
2 6729717 3880 62689 108
2 5378015 14554 21859 109
2 7725561 32716 52949 110
2 2310467 40502 59703 111
2 666730429 36232 36617 112
2 7559620 22858 40523 112
3 4609475 112
2 2548415 2234 25411 113
2 6658866 54164 73418 114
2 1439857 15031 33645 115
2 9710473 49046 67877 116
2 264147 582 44551 117
4 2174 14 4795
3 4032861 116
3 8394636 115
2 6109390 53955 78454 116
2 2868226 67171 78042 117
3 4181854 116
2 6394850 80629 81850 117
2 158746 38143 60690 118Editor is loading...
Leave a Comment