# biweekly-contest-36

## A

### Statement

• Difficulty: Easy
• Tag: `设计` `计数` `模拟`

• `ParkingSystem(int big, int medium, int small)` 初始化 `ParkingSystem` 类，三个参数分别对应每种停车位的数目。
• `bool addCar(int carType)` 检查是否有 `carType` 对应的停车位。 `carType` 有三种类型：大，中，小，分别用数字 `1`， `2` 和 `3` 表示。一辆车只能停在  `carType` 对应尺寸的停车位中。如果没有空车位，请返回 `false` ，否则将该车停入车位并返回 `true` 。

``````输入：
[[1, 1, 0], [1], [2], [3], [1]]

[null, true, true, false, false]

ParkingSystem parkingSystem = new ParkingSystem(1, 1, 0);
parkingSystem.addCar(1); // 返回 true ，因为有 1 个空的大车位
parkingSystem.addCar(2); // 返回 true ，因为有 1 个空的中车位
``````

• `0 <= big, medium, small <= 1000`
• `carType` 取值为 `1`， `2` 或 `3`
• 最多会调用 `addCar` 函数 `1000` 次

• Difficulty: Easy
• Tag: `Design` `Counting` `Simulation`

Design a parking system for a parking lot. The parking lot has three kinds of parking spaces: big, medium, and small, with a fixed number of slots for each size.

Implement the `ParkingSystem` class:

• `ParkingSystem(int big, int medium, int small)` Initializes object of the `ParkingSystem` class. The number of slots for each parking space are given as part of the constructor.
• `bool addCar(int carType)` Checks whether there is a parking space of `carType` for the car that wants to get into the parking lot. `carType` can be of three kinds: big, medium, or small, which are represented by `1`, `2`, and `3` respectively. A car can only park in a parking space of its `carType`. If there is no space available, return `false`, else park the car in that size space and return `true`.

Example 1:

``````Input
[[1, 1, 0], [1], [2], [3], [1]]
Output
[null, true, true, false, false]
Explanation
ParkingSystem parkingSystem = new ParkingSystem(1, 1, 0);
parkingSystem.addCar(1); // return true because there is 1 available slot for a big car
parkingSystem.addCar(2); // return true because there is 1 available slot for a medium car
parkingSystem.addCar(3); // return false because there is no available slot for a small car
parkingSystem.addCar(1); // return false because there is no available slot for a big car. It is already occupied.
``````

Constraints:

• `0 <= big, medium, small <= 1000`
• `carType` is `1`, `2`, or `3`
• At most `1000` calls will be made to `addCar`

### Solution

``````#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
x += y;
while (x >= Mod) x -= Mod;
while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
if (x < y)
x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
if (x > y)
x = y;
}
inline int nextInt() {
int x;
cin >> x;
return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
cin >> arg;
rd(args...);
}
#define dbg(x...)                             \
do {                                      \
cout << "\033[32;1m" << #x << " -> "; \
err(x);                               \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
cout << arg << ' ';
err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
for (auto &v : arg) cout << v << ' ';
err(args...);
}
void ptt() {
cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
cout << ' ' << arg;
ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
cout << arg;
ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
pt(args...);
}
inline ll qpow(ll base, ll n) {
assert(n >= 0);
ll res = 1;
while (n) {
if (n & 1)
res = res * base % mod;
base = base * base % mod;
n >>= 1;
}
return res;
}
constexpr int N = 1e5 + 10;
int n;

class ParkingSystem {
public:
int x[4];
ParkingSystem(int big, int medium, int small) {
x[1] = big;
x[2] = medium;
x[3] = small;
}

if (x[carType] <= 0)
return false;
else {
--x[carType];
return true;
}
}
};

/**
* Your ParkingSystem object will be instantiated and called as such:
* ParkingSystem* obj = new ParkingSystem(big, medium, small);
*/

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

``````输入：keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]

``````

``````输入：keyName = ["alice","alice","alice","bob","bob","bob","bob"], keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]

``````

``````输入：keyName = ["john","john","john"], keyTime = ["23:58","23:59","00:01"]

``````

``````输入：keyName = ["leslie","leslie","leslie","clare","clare","clare","clare"], keyTime = ["13:00","13:20","14:00","18:00","18:51","19:30","19:49"]

``````

• `1 <= keyName.length, keyTime.length <= 105`
• `keyName.length == keyTime.length`
• `keyTime` 格式为 "HH:MM"
• 保证 `[keyName[i], keyTime[i]]` 形成的二元对 互不相同
• `1 <= keyName[i].length <= 10`
• `keyName[i]` 只包含小写英文字母。

LeetCode company workers use key-cards to unlock office doors. Each time a worker uses their key-card, the security system saves the worker's name and the time when it was used. The system emits an alert if any worker uses the key-card three or more times in a one-hour period.

You are given a list of strings `keyName` and `keyTime` where `[keyName[i], keyTime[i]]` corresponds to a person's name and the time when their key-card was used in a single day.

Access times are given in the 24-hour time format "HH:MM", such as `"23:51"` and `"09:49"`.

Return a list of unique worker names who received an alert for frequent keycard use. Sort the names in ascending order alphabetically.

Notice that `"10:00"` - `"11:00"` is considered to be within a one-hour period, while `"22:51"` - `"23:52"` is not considered to be within a one-hour period.

Example 1:

``````Input: keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]
Output: ["daniel"]
Explanation: "daniel" used the keycard 3 times in a one-hour period ("10:00","10:40", "11:00").
``````

Example 2:

``````Input: keyName = ["alice","alice","alice","bob","bob","bob","bob"], keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]
Output: ["bob"]
Explanation: "bob" used the keycard 3 times in a one-hour period ("21:00","21:20", "21:30").
``````

Constraints:

• `1 <= keyName.length, keyTime.length <= 105`
• `keyName.length == keyTime.length`
• `keyTime[i]` is in the format "HH:MM".
• `[keyName[i], keyTime[i]]` is unique.
• `1 <= keyName[i].length <= 10`
• `keyName[i] contains only lowercase English letters.`

### Solution

``````#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
x += y;
while (x >= Mod) x -= Mod;
while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
if (x < y)
x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
if (x > y)
x = y;
}
inline int nextInt() {
int x;
cin >> x;
return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
cin >> arg;
rd(args...);
}
#define dbg(x...)                             \
do {                                      \
cout << "\033[32;1m" << #x << " -> "; \
err(x);                               \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
cout << arg << ' ';
err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
for (auto &v : arg) cout << v << ' ';
err(args...);
}
void ptt() {
cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
cout << ' ' << arg;
ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
cout << arg;
ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
pt(args...);
}
inline ll qpow(ll base, ll n) {
assert(n >= 0);
ll res = 1;
while (n) {
if (n & 1)
res = res * base % mod;
base = base * base % mod;
n >>= 1;
}
return res;
}
constexpr int N = 1e5 + 10;
int n;

int toInt(char c) {
return c - '0';
}

int change(string time) {
int res = (toInt(time[0]) * 10 + toInt(time[1])) * 60 + toInt(time[3]) * 10 + toInt(time[4]);
return res;
}

class Solution {
public:
vector<string> alertNames(vector<string> &keyName, vector<string> &keyTime) {
map<string, vector<int>> mp;
n = SZ(keyName);
for (int i = 0; i < n; ++i) {
string name = keyName[i];
string time = keyTime[i];
if (mp.count(name) == 0)
mp[name] = vector<int>();
mp[name].push_back(change(time));
}
vector<string> res;
for (auto &it : mp) {
sort(all(it.se));
int ok = 0;
for (int i = 2; i < SZ(it.se); ++i) {
if (it.se[i] - it.se[i - 2] <= 60) {
ok = 1;
break;
}
}
if (ok)
res.push_back(it.fi);
}
sort(all(res));
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

``````输入：rowSum = [3,8], colSum = [4,7]

[1,7]]

[3,5]]
``````

``````输入：rowSum = [5,7,10], colSum = [8,6,8]

[6,1,0],
[2,0,8]]
``````

``````输入：rowSum = [14,9], colSum = [6,9,8]

[6,0,3]]
``````

``````输入：rowSum = [1,0], colSum = [1]

[0]]
``````

``````输入：rowSum = [0], colSum = [0]

``````

• `1 <= rowSum.length, colSum.length <= 500`
• `0 <= rowSum[i], colSum[i] <= 108`
• `sum(rows) == sum(columns)`

You are given two arrays `rowSum` and `colSum` of non-negative integers where `rowSum[i]` is the sum of the elements in the `ith` row and `colSum[j]` is the sum of the elements of the `jth` column of a 2D matrix. In other words, you do not know the elements of the matrix, but you do know the sums of each row and column.

Find any matrix of non-negative integers of size `rowSum.length x colSum.length` that satisfies the `rowSum` and `colSum` requirements.

Return a 2D array representing any matrix that fulfills the requirements. It's guaranteed that at least one matrix that fulfills the requirements exists.

Example 1:

``````Input: rowSum = [3,8], colSum = [4,7]
Output: [[3,0],
[1,7]]
Explanation:
0th row: 3 + 0 = 3 == rowSum[0]
1st row: 1 + 7 = 8 == rowSum[1]
0th column: 3 + 1 = 4 == colSum[0]
1st column: 0 + 7 = 7 == colSum[1]
The row and column sums match, and all matrix elements are non-negative.
Another possible matrix is: [[1,2],
[3,5]]
``````

Example 2:

``````Input: rowSum = [5,7,10], colSum = [8,6,8]
Output: [[0,5,0],
[6,1,0],
[2,0,8]]
``````

Constraints:

• `1 <= rowSum.length, colSum.length <= 500`
• `0 <= rowSum[i], colSum[i] <= 108`
• `sum(rows) == sum(columns)`

### Solution

``````#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1& x, T2 y, int Mod = mod) {
x += y;
while (x >= Mod) x -= Mod;
while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1& x, T2 y) {
if (x < y)
x = y;
}
template <class T1, class T2>
inline void chmin(T1& x, T2 y) {
if (x > y)
x = y;
}
inline int nextInt() {
int x;
cin >> x;
return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T& arg, Ts&... args) {
cin >> arg;
rd(args...);
}
#define dbg(x...)                             \
do {                                      \
cout << "\033[32;1m" << #x << " -> "; \
err(x);                               \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
cout << arg << ' ';
err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t>& arg, const A&... args) {
for (auto& v : arg) cout << v << ' ';
err(args...);
}
void ptt() {
cout << endl;
}
template <class T, class... Ts>
void ptt(const T& arg, const Ts&... args) {
cout << ' ' << arg;
ptt(args...);
}
template <class T, class... Ts>
void pt(const T& arg, const Ts&... args) {
cout << arg;
ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t>& arg, const A&... args) {
for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
pt(args...);
}
inline ll qpow(ll base, ll n) {
assert(n >= 0);
ll res = 1;
while (n) {
if (n & 1)
res = res * base % mod;
base = base * base % mod;
n >>= 1;
}
return res;
}
constexpr int N = 1e5 + 10;
int n, m;

class Solution {
public:
vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {
n = SZ(rowSum);
m = SZ(colSum);
vector<vector<int>> res(n, vector<int>(m, 0));
//	vector <int> _rowSum(n, 0);
//	vector <int> _colSum(m, 0);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int x = min(rowSum[i], colSum[j]);
res[i][j] = x;
rowSum[i] -= x;
colSum[j] -= x;
}
}
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

• 第 `i` （序号从 0 开始）个请求到达。
• 如果所有服务器都已被占据，那么该请求被舍弃（完全不处理）。
• 如果第 `(i % k)` 个服务器空闲，那么对应服务器会处理该请求。
• 否则，将请求安排给下一个空闲的服务器（服务器构成一个环，必要的话可能从第 0 个服务器开始继续找下一个空闲的服务器）。比方说，如果第 `i` 个服务器在忙，那么会查看第 `(i+1)` 个服务器，第 `(i+2)` 个服务器等等。

``````输入：k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3]

``````

``````输入：k = 3, arrival = [1,2,3,4], load = [1,2,1,2]

``````

``````输入：k = 3, arrival = [1,2,3], load = [10,12,11]

``````

``````输入：k = 3, arrival = [1,2,3,4,8,9,10], load = [5,2,10,3,1,2,2]

``````

``````输入：k = 1, arrival = [1], load = [1]

``````

• `1 <= k <= 105`
• `1 <= arrival.length, load.length <= 105`
• `arrival.length == load.length`
• `1 <= arrival[i], load[i] <= 109`
• `arrival` 保证 严格递增 。

You have `k` servers numbered from `0` to `k-1` that are being used to handle multiple requests simultaneously. Each server has infinite computational capacity but cannot handle more than one request at a time. The requests are assigned to servers according to a specific algorithm:

• The `ith` (0-indexed) request arrives.
• If all servers are busy, the request is dropped (not handled at all).
• If the `(i % k)th` server is available, assign the request to that server.
• Otherwise, assign the request to the next available server (wrapping around the list of servers and starting from 0 if necessary). For example, if the `ith` server is busy, try to assign the request to the `(i+1)th` server, then the `(i+2)th` server, and so on.

You are given a strictly increasing array `arrival` of positive integers, where `arrival[i]` represents the arrival time of the `ith` request, and another array `load`, where `load[i]` represents the load of the `ith` request (the time it takes to complete). Your goal is to find the busiest server(s). A server is considered busiest if it handled the most number of requests successfully among all the servers.

Return a list containing the IDs (0-indexed) of the busiest server(s). You may return the IDs in any order.

Example 1:

``````Input: k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3]
Output: [1]
Explanation:
All of the servers start out available.
The first 3 requests are handled by the first 3 servers in order.
Request 3 comes in. Server 0 is busy, so it's assigned to the next available server, which is 1.
Request 4 comes in. It cannot be handled since all servers are busy, so it is dropped.
Servers 0 and 2 handled one request each, while server 1 handled two requests. Hence server 1 is the busiest server.
``````

Example 2:

``````Input: k = 3, arrival = [1,2,3,4], load = [1,2,1,2]
Output: [0]
Explanation:
The first 3 requests are handled by first 3 servers.
Request 3 comes in. It is handled by server 0 since the server is available.
Server 0 handled two requests, while servers 1 and 2 handled one request each. Hence server 0 is the busiest server.
``````

Example 3:

``````Input: k = 3, arrival = [1,2,3], load = [10,12,11]
Output: [0,1,2]
Explanation: Each server handles a single request, so they are all considered the busiest.
``````

Constraints:

• `1 <= k <= 105`
• `1 <= arrival.length, load.length <= 105`
• `arrival.length == load.length`
• `1 <= arrival[i], load[i] <= 109`
• `arrival` is strictly increasing.

### Solution

``````#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
using pLI = pair<ll, int>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1& x, T2 y, int Mod = mod) {
x += y;
while (x >= Mod) x -= Mod;
while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1& x, T2 y) {
if (x < y)
x = y;
}
template <class T1, class T2>
inline void chmin(T1& x, T2 y) {
if (x > y)
x = y;
}
inline int nextInt() {
int x;
cin >> x;
return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T& arg, Ts&... args) {
cin >> arg;
rd(args...);
}
#define dbg(x...)                             \
do {                                      \
cout << "\033[32;1m" << #x << " -> "; \
err(x);                               \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
cout << arg << ' ';
err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t>& arg, const A&... args) {
for (auto& v : arg) cout << v << ' ';
err(args...);
}
void ptt() {
cout << endl;
}
template <class T, class... Ts>
void ptt(const T& arg, const Ts&... args) {
cout << ' ' << arg;
ptt(args...);
}
template <class T, class... Ts>
void pt(const T& arg, const Ts&... args) {
cout << arg;
ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t>& arg, const A&... args) {
for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
pt(args...);
}
inline ll qpow(ll base, ll n) {
assert(n >= 0);
ll res = 1;
while (n) {
if (n & 1)
res = res * base % mod;
base = base * base % mod;
n >>= 1;
}
return res;
}
constexpr int N = 1e5 + 10;
int n, f[N];

class Solution {
public:
vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {
vector<int> res;
n = SZ(arrival);
set<int> se;
for (int i = 0; i < k; ++i) {
se.insert(i);
}
memset(f, 0, sizeof f);
priority_queue<pLI, vector<pLI>, greater<pLI>> pq;
for (int i = 0; i < n; ++i) {
ll now = arrival[i];
while (!pq.empty() && pq.top().fi <= now) {
se.insert(pq.top().se);
pq.pop();
}
if (se.empty())
continue;
int x = i % k;
auto pos = se.lower_bound(x);
if (pos == se.end())
pos = se.begin();
++f[*pos];
se.erase(pos);
}
int Max = 0;
for (int i = 0; i < k; ++i) {
if (f[i] > Max) {
res.clear();
Max = f[i];
res.push_back(i);
} else if (f[i] == Max) {
res.push_back(i);
}
}
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````