Untitled
unknown
plain_text
2 years ago
13 kB
12
Indexable
The capacity of the parking lot and the price table are given.
When a car arrives, it is parked inside the parking lot if there is a space. If the parking lot is full, the car waits outside.
When a car that was parked in the lot exits, the car owner pays the fee as in the price table.
When there are cars waiting, the car with the biggest value of subtracting the total parking time from the total waiting time
(Total waiting time - Total parking time) among them is allowed to enter into the lot.
If there are two or more cars with the biggest value of (Total waiting time - Total parking time),
the car which is in front of the other ones in the waiting line enters into the lot.
The price table consists of base time, base fee, unit time, and unit fee.
Parking time less or equal to the base time will cost only the base fee.
Once it exceeds the base time, unit fee is charged every unit time.
In this case, when the exceeded time cannot be divided by unit time, round it up.
For instance, let’s look into a case when the price table is as in [Table 1] below.
Base Time
Base Fee
Unit Time
Unit Fee
60
5000
20
300
[Table 1]
When the parking time is 50, the parking fee will be 5000.
When the parking time is 85, it will be 5600 by calculating 5000 + ceil( (85 - 60) / 20 ) x 300.
(ceil in here refers to the function rounded up.)
You are required to implement a parking managing system that operates as above.
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 mBaseTime, int mBaseFee, int mUnitTime, int mUnitFee, int mCapacity)
This function is called in the beginning of each test case.
This function empties the parking lot.
The base time is mBaseTime, the base fee is mBaseFee, the unit time is mUnitTime, and the unit fee is mUnitFee.
In addition, the capacity of the parking lot is mCapacity.
Parameters
mBaseTime: The base time ( 60 ≤ mBaseTime ≤ 180 )
mBaseFee: The base fee ( 1,000 ≤ mBaseFee ≤ 20,000 )
mUnitTime: The unit time ( 20 ≤ mUnitTime ≤ 120 )
mUnitFee: The unit fee ( 300 ≤ mUnitFee ≤ 10,000 )
mCapacity: The capacity of the parking lot ( 5 ≤ mCapacity ≤ 200 )
int arrive(int mTime, int mCar)
This function makes mCar arrive at mTime.
There is NO case when mCar is given as a car number that is parked or waiting.
When the parking lot is NOT full, this function lets the car enter into the parking lot. If not, this function puts the car in the waiting line.
This function returns the number of cars waiting.
Please note that the car that came to the parking lot before can return.
Parameters
mTime: The arrival time ( 1 ≤ mTime ≤ 300,000 )
mCar: The car number ( 1 ≤ mCar ≤ 1,000,000,000 )
Returns
Return the number of cars waiting. If there are none, return 0.
int leave(int mTime, int mCar)
This function makes mCar leave the parking lot at mTime.
mCar is given only as a car number that is parked or waiting.
This function returns the parking fee when mCar was parked. In addition, among the cars waiting, this function lets the car with the biggest value of (Total waiting time - Total parking time) enter into the parking lot. When there are two or more of such a car, this function lets the car that was added earlier in the waiting line enter into the parking lot. (Please note that Car B is processed to have been added to the waiting line earlier than Car A when Car A was deleted and then added again in the waiting line after Cars A and B were added to the waiting line in order.)
When mCar was waiting, this function deletes it in the waiting line and returns -1.
Parameters
mTime: The exit time ( 1 ≤ mTime ≤ 300,000 )
mCar: The car number ( 1 ≤ mCar ≤ 1,000,000,000 )
Returns
When the car was parked, return the parking fee.
When the car was waiting, return -1.
[Example]
Let’s look into a case where functions are called as in [Table 2] below.
Order
Function
return
Figure
1
init(60, 5000, 20, 300, 5)
2
arrive(10, 200)
0
3
arrive(30, 100)
0
4
arrive(50, 700)
0
5
arrive(80, 600)
0
Fig. 1
6
leave(90, 200)
5300
Fig. 2
7
arrive(100, 300)
0
8
arrive(120, 800)
0
Fig. 3
9
arrive(140, 200)
1
Fig. 4
10
arrive(170, 400)
2
Fig. 5
11
arrive(240, 900)
3
Fig. 6
12
leave(300, 300)
7100
Fig. 7
13
leave(310, 900)
-1
Fig. 8
14
leave(340, 100)
8900
Fig. 9
15
arrive(350, 500)
1
Fig. 10
16
arrive(400, 900)
2
Fig. 11
17
leave(420, 200)
5300
Fig. 12
18
leave(450, 900)
5000
Fig. 13
[Table 2]
(Order 1) In the beginning, the parking lot and the waiting line is empty.
The parking price table is given as in [Table 1]. The capacity of the parking lot is 5.
(Order 2) At Time 10, Car 200 arrives. It enters into the parking lot. As there is NO car waiting, return 0.
(Order 3) At Time 30, Car 100 arrives. It enters into the parking lot. As there is NO car waiting, return 0.
(Order 4) At Time 50, Car 700 arrives. It enters into the parking lot. As there is NO car waiting, return 0.
(Order 5) At Time 80, Car 600 arrives. It enters into the parking lot. As there is NO car waiting, return 0.
[Fig. 1] shows the result of function call.
[Fig. 1]
(Order 6) At Time 90, Car 200 leaves the parking lot. As it was parked, calculate the parking fee.
The parking fee is 5300 by calculating 5000 + ceil( (80 - 60) / 20 ) x 300. [Fig. 2] shows the result of function call.
[Fig. 2]
(Order 7) At Time 100, Car 300 arrives. It enters into the parking lot. As there is NO car waiting, return 0.
(Order 8) At Time 120, Car 800 arrives. It enters into the parking lot. As there is NO car waiting, return 0.
[Fig. 3] shows the result of function call.
[Fig. 3]
(Order 9) At Time 140, Car 200 arrives. As the parking lot is full, the car waits.
There is only 1 car waiting, which is Car 200. Thus, return 1. [Fig. 4] shows the result of function call.
[Fig. 4]
(Order 10) At Time 170, Car 400 arrives. As the parking lot is full, the car waits.
For the number of cars waiting, return 2. [Fig. 5] shows the result of function call.
[Fig. 5]
(Order 11) At Time 240, Car 900 arrives. As the parking lot is full, the car waits.
For the number of cars waiting, return 3. [Fig. 6] shows the result of function call.
[Fig. 6]
(Order 12) At Time 300, Car 300 leaves the parking lot. As it was parked, calculate the parking fee.
The parking fee is 7100 by calculating 5000 + ceil( (200 - 60) / 20 ) x 300.
Among the cars waiting, Car 400 has the biggest value of (Total waiting time - Total parking time).
Thus, let Car 400 enter into the parking lot. [Fig. 7] shows the result of function call.
[Fig. 7]
(Order 13) At Time 310, Car 900 leaves the parking lot. As it was waiting, delete it from the waiting line and return -1.
[Fig. 8] shows the result of function call.
[Fig. 8]
(Order 14) At Time 340, Car 100 leaves the parking lot. As it was parked, calculate the parking fee.
The parking fee is 8900 by calculating 5000 + ceil( (310 - 60) / 20 ) x 300.
There is only 1 car waiting, which is Car 200. Thus, let Car 200 enter into the parking lot.
[Fig. 9] shows the result of function call.
[Fig. 9]
(Order 15) At Time 350, Car 500 arrives. As the parking lot is full, the car waits.
There is only 1 car waiting, which is Car 500. Thus, return 1. [Fig. 10] shows the result of function call.
[Fig. 10]
(Order 16) At Time 400, Car 900 arrives. As the parking lot is full, the car waits.
For the number of cars waiting, return 2. [Fig. 11] shows the result of function call.
[Fig. 11]
(Order 17) At Time 420, Car 200 leaves the parking lot. As it was parked, calculate the parking fee.
The parking fee is 5300 by calculating 5000 + ceil( (80 - 60) / 20 ) x 300.
Among the cars waiting, Car 900 has the biggest value of (Total waiting time - Total parking time).
Thus, let Car 900 enter into the parking lot. [Fig. 12] shows the result of function call.
[Fig. 12]
(Order 18) At Time 450, Car 900 leaves the parking lot. As it was parked, calculate the parking fee.
The parking fee is 5000. There is only 1 car waiting, which is Car 500.
Thus, let Car 500 enter into the parking lot. [Fig. 13] shows the result of function call.
[Fig. 13]
[Constraints]
1. init() is called in the beginning of each test case.
2. For each test case, mTime is given as a value that is increasing.
3. For each test case, arrive() is called up to 70,000 times.
4. For each test case, the sum of calls of the all functions is less than or equal to 100,000.
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
extern void init(int mBaseTime, int mBaseFee, int mUnitTime, int mUnitFee, int mCapacity);
extern int arrive(int mTime, int mCar);
extern int leave(int mTime, int mCar);
/////////////////////////////////////////////////////////////////////////
#define CMD_INIT 1
#define CMD_ARRIVE 2
#define CMD_LEAVE 3
static bool run() {
int q;
scanf("%d", &q);
int basetime, basefee, unittime, unitfee, capacity, mtime, mcar;
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 %d %d %d", &basetime, &basefee, &unittime, &unitfee, &capacity);
init(basetime, basefee, unittime, unitfee, capacity);
okay = true;
break;
case CMD_ARRIVE:
scanf("%d %d %d", &mtime, &mcar, &ans);
ret = arrive(mtime, mcar);
printf("%d\n", ret);
if (ans != ret)
okay = false;
break;
case CMD_LEAVE:
scanf("%d %d %d", &mtime, &mcar, &ans);
ret = leave(mtime, mcar);
printf("%d\n", ret);
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;
}
#include <set>
#include <unordered_map>
#include <cmath>
using namespace std;
struct car{
int begin;
int parkingTime;
int waitTime;
int id;
int status;
} pool[70005];
struct CMP{
bool operator()(int a, int b){
if(pool[a].begin + pool[a].parkingTime != pool[b].begin+ pool[b].parkingTime) return pool[a].begin + pool[a].parkingTime < pool[b].begin+ pool[b].parkingTime;
return pool[a].begin < pool[b].begin;
}
};
set<int, CMP> waitQueue;
unordered_map<int, int> search;
int baseTime, baseFee, unitTime, unitFee;
int avai;
int idx;
void init(int mBaseTime, int mBaseFee, int mUnitTime, int mUnitFee, int mCapacity) {
avai=mCapacity;
baseTime=mBaseTime;
baseFee=mBaseFee;
unitTime=mUnitTime;
unitFee=mUnitFee;
idx=1;
waitQueue.clear();
return;
}
int arrive(int mTime, int mCar) {
if(avai>0){
avai--;
if(!search[mCar]){
pool[idx].begin=mTime;
pool[idx].id=idx;
pool[idx].parkingTime=0;
pool[idx].waitTime=0;
pool[idx].status=1;
search[mCar]=idx++;
}
else{
int id=search[mCar];
pool[id].begin=mTime;
pool[id].status=1;
}
}
else{
if(!search[mCar]){
pool[idx].begin=mTime;
pool[idx].id=idx;
pool[idx].parkingTime=0;
pool[idx].status=0;
waitQueue.insert(idx);
search[mCar]=idx++;
}
else{
int id=search[mCar];
pool[id].begin=mTime;
pool[id].status=0;
waitQueue.insert(id);
}
}
return waitQueue.size();
}
int leave(int mTime, int mCar) {
int id=search[mCar];
if(pool[id].status==0){
waitQueue.erase(id);
return -1;
}
else{
pool[id].status=0;
avai++;
if(!waitQueue.empty()){
int id2=*waitQueue.begin();
avai--;
waitQueue.erase(id2);
pool[id2].begin=mTime;
pool[id2].status=1;
}
pool[id].parkingTime+=mTime-pool[id].begin;
if(pool[id].parkingTime <= baseTime) return baseFee;
else{
if((pool[id].parkingTime - baseTime) % unitTime==0) return baseFee+ (pool[id].parkingTime - baseTime)/unitTime*unitFee;
return baseFee+ (1+(pool[id].parkingTime - baseTime)/unitTime)*unitFee;
}
}
return -1;
}
25 100
18
1 60 5000 20 300 5
2 10 200 0
2 30 100 0
2 50 700 0
2 80 600 0
3 90 200 5300
2 100 300 0
2 120 800 0
2 140 200 1
2 170 400 2
2 240 900 3
3 300 300 7100
3 310 900 -1
3 340 100 8900
2 350 500 1
2 400 900 2
3 420 200 5300
3 450 900 5000
Editor is loading...