# weekly-contest-309

## A

### Statement

``````输入：s = "abaccb", distance = [1,3,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

- 'a' 在下标 0 和下标 2 处出现，所以满足 distance[0] = 1 。
- 'b' 在下标 1 和下标 5 处出现，所以满足 distance[1] = 3 。
- 'c' 在下标 3 和下标 4 处出现，所以满足 distance[2] = 0 。

``````

``````输入：s = "aa", distance = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

- 'a' 在下标 0 和 1 处出现，所以两次出现之间的字母数量为 0 。

``````

• `2 <= s.length <= 52`
• `s` 仅由小写英文字母组成
• `s` 中的每个字母恰好出现两次
• `distance.length == 26`
• `0 <= distance[i] <= 50`

You are given a 0-indexed string `s` consisting of only lowercase English letters, where each letter in `s` appears exactly twice. You are also given a 0-indexed integer array `distance` of length `26`.

Each letter in the alphabet is numbered from `0` to `25` (i.e. `'a' -> 0`, `'b' -> 1`, `'c' -> 2`, … , `'z' -> 25`).

In a well-spaced string, the number of letters between the two occurrences of the `ith` letter is `distance[i]`. If the `ith` letter does not appear in `s`, then `distance[i]` can be ignored.

Return `true` if `s` is a well-spaced string, otherwise return `false`.

Example 1:

``````Input: s = "abaccb", distance = [1,3,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: true
Explanation:
- 'a' appears at indices 0 and 2 so it satisfies distance[0] = 1.
- 'b' appears at indices 1 and 5 so it satisfies distance[1] = 3.
- 'c' appears at indices 3 and 4 so it satisfies distance[2] = 0.
Note that distance[3] = 5, but since 'd' does not appear in s, it can be ignored.
Return true because s is a well-spaced string.
``````

Example 2:

``````Input: s = "aa", distance = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: false
Explanation:
- 'a' appears at indices 0 and 1 so there are zero letters between them.
Because distance[0] = 1, s is not a well-spaced string.
``````

Constraints:

• `2 <= s.length <= 52`
• `s` consists only of lowercase English letters.
• Each letter appears in `s` exactly twice.
• `distance.length == 26`
• `0 <= distance[i] <= 50`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
bool checkDistances(string s, vector<int> &distance) {
auto f = vector<int>(300, -1);
for (size_t i = 0; i < s.length(); i++) {
int c = s[i] - 'a';
if (f[c] != -1) {
if (i - f[c] - 1 != distance[c]) {
return false;
}
}

f[c] = i;
}

return true;
}
};
#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

``````输入：startPos = 1, endPos = 2, k = 3

- 1 -> 2 -> 3 -> 2.
- 1 -> 2 -> 1 -> 2.
- 1 -> 0 -> 1 -> 2.

``````输入：startPos = 2, endPos = 5, k = 10

• `1 <= startPos, endPos, k <= 1000`

You are given two positive integers `startPos` and `endPos`. Initially, you are standing at position `startPos` on an infinite number line. With one step, you can move either one position to the left, or one position to the right.

Given a positive integer `k`, return the number of different ways to reach the position `endPos` starting from `startPos`, such that you perform exactly `k` steps. Since the answer may be very large, return it modulo `109 + 7`.

Two ways are considered different if the order of the steps made is not exactly the same.

Note that the number line includes negative integers.

Example 1:

``````Input: startPos = 1, endPos = 2, k = 3
Output: 3
Explanation: We can reach position 2 from 1 in exactly 3 steps in three ways:
- 1 -> 2 -> 3 -> 2.
- 1 -> 2 -> 1 -> 2.
- 1 -> 0 -> 1 -> 2.
It can be proven that no other way is possible, so we return 3.``````

Example 2:

``````Input: startPos = 2, endPos = 5, k = 10
Output: 0
Explanation: It is impossible to reach position 5 from position 2 in exactly 10 steps.
``````

Constraints:

• `1 <= startPos, endPos, k <= 1000`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

const int MOD = 1e9 + 7;

class Solution {
public:
int offset(int x) {
return x + 1050;
}

int numberOfWays(int startPos, int endPos, int k) {
int gap = abs(startPos - endPos);
if ((gap & 1) != (k & 1)) {
return 0;
}

auto f = vector<vector<int>>(3100, vector<int>(k + 5, 0));
auto visit = vector<vector<int>>(3100, vector<int>(k + 5, 0));

auto q = queue<pair<int, int>>();

auto st = make_pair(offset(startPos), 0);
f[st.first][st.second] = 1;
q.push(st);

while (!q.empty()) {
auto p = q.front();
q.pop();

if (p.second == k) {
continue;
}

{
auto _p = p;
_p.first++;
_p.second++;
f[_p.fi][_p.se] += f[p.fi][p.se];
f[_p.fi][_p.se] %= MOD;
if (!visit[_p.fi][_p.se]) {
q.push(_p);
visit[_p.fi][_p.se] = true;
}
}

{
auto _p = p;
_p.first--;
_p.second++;
f[_p.fi][_p.se] += f[p.fi][p.se];
f[_p.fi][_p.se] %= MOD;
if (!visit[_p.fi][_p.se]) {
q.push(_p);
visit[_p.fi][_p.se] = true;
}
}
}

auto ed = make_pair(offset(endPos), k);
return f[ed.fi][ed.se];
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

``````输入：nums = [1,3,8,48,10]

- 3 AND 8 = 0
- 3 AND 48 = 0
- 8 AND 48 = 0

``````输入：nums = [3,1,5,11,13]

``````

• `1 <= nums.length <= 105`
• `1 <= nums[i] <= 109`

You are given an array `nums` consisting of positive integers.

We call a subarray of `nums` nice if the bitwise AND of every pair of elements that are in different positions in the subarray is equal to `0`.

Return the length of the longest nice subarray.

A subarray is a contiguous part of an array.

Note that subarrays of length `1` are always considered nice.

Example 1:

``````Input: nums = [1,3,8,48,10]
Output: 3
Explanation: The longest nice subarray is [3,8,48]. This subarray satisfies the conditions:
- 3 AND 8 = 0.
- 3 AND 48 = 0.
- 8 AND 48 = 0.
It can be proven that no longer nice subarray can be obtained, so we return 3.``````

Example 2:

``````Input: nums = [3,1,5,11,13]
Output: 1
Explanation: The length of the longest nice subarray is 1. Any subarray of length 1 can be chosen.
``````

Constraints:

• `1 <= nums.length <= 105`
• `1 <= nums[i] <= 109`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
int longestNiceSubarray(vector<int> &a) {
int n = int(a.size());
int l = 0;
int s = a[0];
int res = 1;
for (int i = 1; i < n; i++) {
while (s & a[i]) {
s ^= a[l];
++l;
}
s ^= a[i];
res = max(res, i - l + 1);
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

1. 每场会议都会在未占用且编号 最小 的会议室举办。
2. 如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。延期会议的持续时间和原会议持续时间 相同
3. 当会议室处于未占用状态时，将会优先提供给原 开始 时间更早的会议。

``````输入：n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]

- 在时间 0 ，两个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 1 ，只有会议室 1 未占用，第二场会议在会议室 1 举办。
- 在时间 2 ，两个会议室都被占用，第三场会议延期举办。
- 在时间 3 ，两个会议室都被占用，第四场会议延期举办。
- 在时间 5 ，会议室 1 的会议结束。第三场会议在会议室 1 举办，时间周期为 [5,10) 。
- 在时间 10 ，两个会议室的会议都结束。第四场会议在会议室 0 举办，时间周期为 [10,11) 。

``````

``````输入：n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]

- 在时间 1 ，所有三个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 2 ，会议室 1 和 2 未占用，第二场会议在会议室 1 举办。
- 在时间 3 ，只有会议室 2 未占用，第三场会议在会议室 2 举办。
- 在时间 4 ，所有三个会议室都被占用，第四场会议延期举办。
- 在时间 5 ，会议室 2 的会议结束。第四场会议在会议室 2 举办，时间周期为 [5,10) 。
- 在时间 6 ，所有三个会议室都被占用，第五场会议延期举办。
- 在时间 10 ，会议室 1 和 2 的会议结束。第五场会议在会议室 1 举办，时间周期为 [10,12) 。

``````

• `1 <= n <= 100`
• `1 <= meetings.length <= 105`
• `meetings[i].length == 2`
• `0 <= starti < endi <= 5 * 105`
• `starti` 的所有值 互不相同

You are given an integer `n`. There are `n` rooms numbered from `0` to `n - 1`.

You are given a 2D integer array `meetings` where `meetings[i] = [starti, endi]` means that a meeting will be held during the half-closed time interval `[starti, endi)`. All the values of `starti` are unique.

Meetings are allocated to rooms in the following manner:

1. Each meeting will take place in the unused room with the lowest number.
2. If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.
3. When a room becomes unused, meetings that have an earlier original start time should be given the room.

Return the number of the room that held the most meetings. If there are multiple rooms, return the room with the lowest number.

A half-closed interval `[a, b)` is the interval between `a` and `b` including `a` and not including `b`.

Example 1:

``````Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0
Explanation:
- At time 0, both rooms are not being used. The first meeting starts in room 0.
- At time 1, only room 1 is not being used. The second meeting starts in room 1.
- At time 2, both rooms are being used. The third meeting is delayed.
- At time 3, both rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 1 finishes. The third meeting starts in room 1 for the time period [5,10).
- At time 10, the meetings in both rooms finish. The fourth meeting starts in room 0 for the time period [10,11).
Both rooms 0 and 1 held 2 meetings, so we return 0.
``````

Example 2:

``````Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
Output: 1
Explanation:
- At time 1, all three rooms are not being used. The first meeting starts in room 0.
- At time 2, rooms 1 and 2 are not being used. The second meeting starts in room 1.
- At time 3, only room 2 is not being used. The third meeting starts in room 2.
- At time 4, all three rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 2 finishes. The fourth meeting starts in room 2 for the time period [5,10).
- At time 6, all three rooms are being used. The fifth meeting is delayed.
- At time 10, the meetings in rooms 1 and 2 finish. The fifth meeting starts in room 1 for the time period [10,12).
Room 0 held 1 meeting while rooms 1 and 2 each held 2 meetings, so we return 1.
``````

Constraints:

• `1 <= n <= 100`
• `1 <= meetings.length <= 105`
• `meetings[i].length == 2`
• `0 <= starti < endi <= 5 * 105`
• All the values of `starti` are unique.

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <queue>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

struct node {
int ix;
ll t;
bool operator<(const node &other) const {
if (t == other.t) {
return ix > other.ix;
}

return t > other.t;
}
};

class Solution {
public:
int mostBooked(int n, vector<vector<int>> &meetings) {
int m = int(meetings.size());
sort(all(meetings));

// cout << "meetings" << endl;
// for (int i = 0; i < m; i++) {
//     cout << meetings[i][0] << " " << meetings[i][1] << endl;
// }

auto f = vector<int>(n, 0);
// auto tm = vector<int>(n, 0);

auto pq = priority_queue<node>();
for (int i = 0; i < n; i++) {
pq.push(node{
.ix = i,
.t = 0,
});
}

for (int i = 0; i < m; i++) {
int dur = meetings[i][1] - meetings[i][0];
ll st = meetings[i][0];

while (!pq.empty() && pq.top().t < st) {
auto top = pq.top();
pq.pop();
top.t = st;
pq.push(top);
}

auto top = pq.top();
pq.pop();

st = max(st, top.t);
++f[top.ix];

top.t = st + dur;
pq.push(top);
}

int mm = 0;
int ix = 0;
// cout << "f" << endl;
for (int i = 0; i < n; i++) {
// cout << i << " " << f[i] << endl;
if (f[i] > mm) {
mm = f[i];
ix = i;
}
}

return ix;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````