# weekly-contest-277

## A

### Statement

Metadata
• Link: 元素计数
• Difficulty: Easy
• Tag: `数组` `排序`

``````输入：nums = [11,7,2,15]

``````

``````输入：nums = [-3,3,3,90]

``````

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

Metadata

Given an integer array `nums`, return the number of elements that have both a strictly smaller and a strictly greater element appear in `nums`.

Example 1:

``````Input: nums = [11,7,2,15]
Output: 2
Explanation: The element 7 has the element 2 strictly smaller than it and the element 11 strictly greater than it.
Element 11 has element 7 strictly smaller than it and element 15 strictly greater than it.
In total there are 2 elements having both a strictly smaller and a strictly greater element appear in nums.
``````

Example 2:

``````Input: nums = [-3,3,3,90]
Output: 2
Explanation: The element 3 has the element -3 strictly smaller than it and the element 90 strictly greater than it.
Since there are two elements with the value 3, in total there are 2 elements having both a strictly smaller and a strictly greater element appear in nums.
``````

Constraints:

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

### 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 lowbit(x) ((x) & (-(x)))
#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>;
const ll mod = 1e9 + 7;

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
// head

class Solution {
public:
int countElements(vector<int> &nums) {
int res = 0;
sort(all(nums));

int Min = nums[0];
int Max = nums.back();

for (auto &a : nums) {
if (Min < a && a < Max) {
++res;
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

Metadata
• Link: 按符号重排数组
• Difficulty: Medium
• Tag: `数组` `双指针` `模拟`

1. 任意 连续 的两个整数 符号相反
2. 对于符号相同的所有整数，保留 它们在 `nums` 中的 顺序
3. 重排后数组以正整数开头。

``````输入：nums = [3,1,-2,-5,2,-4]

nums 中的正整数是 [3,1,2] ，负整数是 [-2,-5,-4] 。

``````

``````输入：nums = [-1,1]

1 是 nums 中唯一一个正整数，-1 是 nums 中唯一一个负整数。

``````

• `2 <= nums.length <= 2 * 105`
• `nums.length`偶数
• `1 <= |nums[i]| <= 105`
• `nums`相等 数量的正整数和负整数组成

Metadata

You are given a 0-indexed integer array `nums` of even length consisting of an equal number of positive and negative integers.

You should rearrange the elements of `nums` such that the modified array follows the given conditions:

1. Every consecutive pair of integers have opposite signs.
2. For all integers with the same sign, the order in which they were present in `nums` is preserved.
3. The rearranged array begins with a positive integer.

Return the modified array after rearranging the elements to satisfy the aforementioned conditions.

Example 1:

``````Input: nums = [3,1,-2,-5,2,-4]
Output: [3,-2,1,-5,2,-4]
Explanation:
The positive integers in nums are [3,1,2]. The negative integers are [-2,-5,-4].
The only possible way to rearrange them such that they satisfy all conditions is [3,-2,1,-5,2,-4].
Other ways such as [1,-2,2,-5,3,-4], [3,1,2,-2,-5,-4], [-2,3,-5,1,-4,2] are incorrect because they do not satisfy one or more conditions.
``````

Example 2:

``````Input: nums = [-1,1]
Output: [1,-1]
Explanation:
1 is the only positive integer and -1 the only negative integer in nums.
So nums is rearranged to [1,-1].
``````

Constraints:

• `2 <= nums.length <= 2 * 105`
• `nums.length` is even
• `1 <= |nums[i]| <= 105`
• `nums` consists of equal number of positive and negative integers.

### 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 lowbit(x) ((x) & (-(x)))
#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>;
const ll mod = 1e9 + 7;

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
// head

class Solution {
public:
vector<int> rearrangeArray(vector<int> &nums) {
vector<int> A, B, res;
for (auto &a : nums) {
if (a > 0) {
A.push_back(a);
} else {
B.push_back(a);
}
}

int n = A.size();
for (int i = 0; i < n; i++) {
res.push_back(A[i]);
res.push_back(B[i]);
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

Metadata

``````输入：nums = [10,6,5,8]

- 10 是一个孤独数字，因为它只出现一次，并且 9 和 11 没有在 nums 中出现。
- 8 是一个孤独数字，因为它只出现一次，并且 7 和 9 没有在 nums 中出现。
- 5 不是一个孤独数字，因为 6 出现在 nums 中，反之亦然。

``````

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

- 1 是一个孤独数字，因为它只出现一次，并且 0 和 2 没有在 nums 中出现。
- 5 是一个孤独数字，因为它只出现一次，并且 4 和 6 没有在 nums 中出现。
- 3 不是一个孤独数字，因为它出现两次。

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

Metadata

You are given an integer array `nums`. A number `x` is lonely when it appears only once, and no adjacent numbers (i.e. `x + 1` and `x - 1)` appear in the array.

Return all lonely numbers in `nums`. You may return the answer in any order.

Example 1:

``````Input: nums = [10,6,5,8]
Output: [10,8]
Explanation:
- 10 is a lonely number since it appears exactly once and 9 and 11 does not appear in nums.
- 8 is a lonely number since it appears exactly once and 7 and 9 does not appear in nums.
- 5 is not a lonely number since 6 appears in nums and vice versa.
Hence, the lonely numbers in nums are [10, 8].
Note that [8, 10] may also be returned.
``````

Example 2:

``````Input: nums = [1,3,5,3]
Output: [1,5]
Explanation:
- 1 is a lonely number since it appears exactly once and 0 and 2 does not appear in nums.
- 5 is a lonely number since it appears exactly once and 4 and 6 does not appear in nums.
- 3 is not a lonely number since it appears twice.
Hence, the lonely numbers in nums are [1, 5].
Note that [5, 1] may also be returned.
``````

Constraints:

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

### 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 lowbit(x) ((x) & (-(x)))
#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>;
const ll mod = 1e9 + 7;

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
// head

const int N = 1e6 + 5;

class Solution {
public:
vector<int> findLonely(vector<int> &nums) {
vector<int> vis(N, 0);
sort(all(nums));
for (auto &c : nums) {
++vis[c];
}

vector<int> res;
for (int i = 0; i < N; i++) {
if (vis[i] == 1 && (i == 0 || vis[i - 1] == 0) && (vis[i + 1] == 0)) {
res.push_back(i);
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

Metadata

• 好人：该角色只说真话。
• 坏人：该角色可能说真话，也可能说假话。

• `0` 表示 `i` 的陈述认为 `j`坏人
• `1` 表示 `i` 的陈述认为 `j`好人
• `2` 表示 `i` 没有对 `j` 作出陈述。

``````输入：statements = [[2,1,2],[1,2,2],[2,0,2]]

- 0 认为 1 是好人。
- 1 认为 0 是好人。
- 2 认为 1 是坏人。

- 假设 2 是一个好人：
- 基于 2 的陈述，1 是坏人。
- 那么可以确认 1 是坏人，2 是好人。
- 基于 1 的陈述，由于 1 是坏人，那么他在陈述时可能：
- 说真话。在这种情况下会出现矛盾，所以假设无效。
- 说假话。在这种情况下，0 也是坏人并且在陈述时说假话。
- 在认为 2 是好人的情况下，这组玩家中只有一个好人。
- 假设 2 是一个坏人：
- 基于 2 的陈述，由于 2 是坏人，那么他在陈述时可能：
- 说真话。在这种情况下，0 和 1 都是坏人。
- 在认为 2 是坏人但说真话的情况下，这组玩家中没有一个好人。
- 说假话。在这种情况下，1 是好人。
- 由于 1 是好人，0 也是好人。
- 在认为 2 是坏人且说假话的情况下，这组玩家中有两个好人。

``````

``````输入：statements = [[2,0],[0,2]]

- 0 认为 1 是坏人。
- 1 认为 0 是坏人。

- 假设 0 是一个好人：
- 基于与 0 的陈述，1 是坏人并说假话。
- 在认为 0 是好人的情况下，这组玩家中只有一个好人。
- 假设 0 是一个坏人：
- 基于 0 的陈述，由于 0 是坏人，那么他在陈述时可能：
- 说真话。在这种情况下，0 和 1 都是坏人。
- 在认为 0 是坏人但说真话的情况下，这组玩家中没有一个好人。
- 说假话。在这种情况下，1 是好人。
- 在认为 0 是坏人且说假话的情况下，这组玩家中只有一个好人。

``````

• `n == statements.length == statements[i].length`
• `2 <= n <= 15`
• `statements[i][j]` 的值为 `0``1``2`
• `statements[i][i] == 2`

Metadata

There are two types of persons:

• The good person: The person who always tells the truth.
• The bad person: The person who might tell the truth and might lie.

You are given a 0-indexed 2D integer array `statements` of size `n x n` that represents the statements made by `n` people about each other. More specifically, `statements[i][j]` could be one of the following:

• `0` which represents a statement made by person `i` that person `j` is a bad person.
• `1` which represents a statement made by person `i` that person `j` is a good person.
• `2` represents that no statement is made by person `i` about person `j`.

Additionally, no person ever makes a statement about themselves. Formally, we have that `statements[i][i] = 2` for all `0 <= i < n`.

Return the maximum number of people who can be good based on the statements made by the `n` people.

Example 1:

``````Input: statements = [[2,1,2],[1,2,2],[2,0,2]]
Output: 2
Explanation: Each person makes a single statement.
- Person 0 states that person 1 is good.
- Person 1 states that person 0 is good.
- Person 2 states that person 1 is bad.
Let's take person 2 as the key.
- Assuming that person 2 is a good person:
- Based on the statement made by person 2, person 1 is a bad person.
- Now we know for sure that person 1 is bad and person 2 is good.
- Based on the statement made by person 1, and since person 1 is bad, they could be:
- telling the truth. There will be a contradiction in this case and this assumption is invalid.
- lying. In this case, person 0 is also a bad person and lied in their statement.
- Following that person 2 is a good person, there will be only one good person in the group.
- Assuming that person 2 is a bad person:
- Based on the statement made by person 2, and since person 2 is bad, they could be:
- telling the truth. Following this scenario, person 0 and 1 are both bad as explained before.
- Following that person 2 is bad but told the truth, there will be no good persons in the group.
- lying. In this case person 1 is a good person.
- Since person 1 is a good person, person 0 is also a good person.
- Following that person 2 is bad and lied, there will be two good persons in the group.
We can see that at most 2 persons are good in the best case, so we return 2.
Note that there is more than one way to arrive at this conclusion.
``````

Example 2:

``````Input: statements = [[2,0],[0,2]]
Output: 1
Explanation: Each person makes a single statement.
- Person 0 states that person 1 is bad.
- Person 1 states that person 0 is bad.
Let's take person 0 as the key.
- Assuming that person 0 is a good person:
- Based on the statement made by person 0, person 1 is a bad person and was lying.
- Following that person 0 is a good person, there will be only one good person in the group.
- Assuming that person 0 is a bad person:
- Based on the statement made by person 0, and since person 0 is bad, they could be:
- telling the truth. Following this scenario, person 0 and 1 are both bad.
- Following that person 0 is bad but told the truth, there will be no good persons in the group.
- lying. In this case person 1 is a good person.
- Following that person 0 is bad and lied, there will be only one good person in the group.
We can see that at most, one person is good in the best case, so we return 1.
Note that there is more than one way to arrive at this conclusion.
``````

Constraints:

• `n == statements.length == statements[i].length`
• `2 <= n <= 15`
• `statements[i][j]` is either `0`, `1`, or `2`.
• `statements[i][i] == 2`

### 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 lowbit(x) ((x) & (-(x)))
#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>;
const ll mod = 1e9 + 7;

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
// head

class Solution {
public:
int maximumGood(vector<vector<int>> &statements) {
int n = statements.size();

auto check = [&](int S) {
vector<int> vis(n + 1, 0);
for (int i = 0; i < n; i++) {
if ((S >> i) & 1) {
vis[i] = 1;
}
}

for (int i = 0; i < n; i++) {
if (vis[i]) {
for (int j = 0; j < n; j++) {
auto sta = statements[i][j];
if (sta == 2) {
continue;
}

if (vis[j] != sta) {
return false;
}
}
}
}

return true;
};

int res = 0;
for (int S = 0; S < 1 << n; ++S) {
if (check(S)) {
chmax(res, bitcnt(S));
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````