A - Partition
Problem Statement
You are given integers
N
N
N and
K
K
K.
The cumulative sums of an integer sequence
X
=
(
X
1
,
X
2
,
…
,
X
N
)
X=(X_1,X_2,\dots ,X_N)
X=(X1,X2,…,XN) of length
N
N
N is defined as a sequence
Y
=
(
Y
0
,
Y
1
,
…
,
Y
N
)
Y=(Y_0,Y_1,\dots ,Y_N)
Y=(Y0,Y1,…,YN) of length
N
+
1
N+1
N+1 as follows:
Y
0
=
0
Y_0=0
Y0=0
Y
i
=
∑
j
=
1
i
X
j
(
i
=
1
,
2
,
…
,
N
)
Y_i=\displaystyle\sum_{j=1}^{i}X_j\ (i=1,2,\dots ,N)
Yi=j=1∑iXj (i=1,2,…,N)
An integer sequence
X
=
(
X
1
,
X
2
,
…
,
X
N
)
X=(X_1,X_2,\dots ,X_N)
X=(X1,X2,…,XN) of length
N
N
N is called a good sequence if and only if it satisfies the following condition:
Any value in the cumulative sums of
X
X
X that is less than
K
K
K appears before any value that is not less than
K
K
K.
Formally, for the cumulative sums
Y
Y
Y of
X
X
X, for any pair of integers
(
i
,
j
)
(i,j)
(i,j) such that
0
≤
i
,
j
≤
N
0 \le i,j \le N
0≤i,j≤N, if KaTeX parse error: Expected 'EOF', got '&' at position 6: (Y_i &̲lt; K and
Y
j
≥
K
)
Y_j \ge K)
Yj≥K), then KaTeX parse error: Expected 'EOF', got '&' at position 3: i &̲lt; j.
You are given an integer sequence
A
=
(
A
1
,
A
2
,
…
,
A
N
)
A=(A_1,A_2,\dots ,A_N)
A=(A1,A2,…,AN) of length
N
N
N. Determine whether the elements of
A
A
A can be rearranged to a good sequence. If so, print one such rearrangement.
Constraints
1
≤
N
≤
2
×
1
0
5
1 \leq N \leq 2 \times 10^5
1≤N≤2×105
−
1
0
9
≤
K
≤
1
0
9
-10^9 \leq K \leq 10^9
−109≤K≤109
−
1
0
9
≤
A
i
≤
1
0
9
-10^9 \leq A_i \leq 10^9
−109≤Ai≤109
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
N
N
K
K
K
A
1
A_1
A1
A
2
A_2
A2
⋯
\cdots
⋯
A
N
A_N
AN
Output
If the elements of A A A can be rearranged to a good sequence, print the rearranged sequence ( A 1 ′ , A 2 ′ , … , A N ′ ) (A^{\prime}_1,A^{\prime}_2,\dots ,A^{\prime}_N) (A1′,A2′,…,AN′) in the following format:
Yes
A
1
′
A^{\prime}_1
A1′
A
2
′
A^{\prime}_2
A2′
⋯
\cdots
⋯
A
N
′
A^{\prime}_N
AN′
If there are multiple valid rearrangements, any of them is considered correct.
If a good sequence cannot be obtained, print No
.
Sample Input 1
4 1
-1 2 -3 4
Sample Output 1
Yes
-3 -1 2 4
If you rearrange A A A to ( − 3 , − 1 , 2 , 4 ) (-3,-1,2,4) (−3,−1,2,4), the cumulative sums Y Y Y in question will be ( 0 , − 3 , − 4 , − 2 , 2 ) (0,-3,-4,-2,2) (0,−3,−4,−2,2). In this Y Y Y, any value less than 1 1 1 appears before any value not less than 1 1 1.
Sample Input 2
4 -1
1 -2 3 -4
Sample Output 2
No
Sample Input 3
10 1000000000
-1000000000 -1000000000 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 3
Yes
-1000000000 -1000000000 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Solution
具体见文末视频。
Code
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n, k, sum = 0;
cin >> n >> k;
std::vector<int> a(n);
for (int i = 0; i < n; i ++)
cin >> a[i], sum += a[i];
if (sum < k && k <= 0) {
cout << "No" << endl;
return 0;
}
if (k > 0) sort(a.begin(), a.end());
else sort(a.begin(), a.end(), greater<int>());
cout << "Yes" << endl;
for (int i = 0; i < n; i ++)
cout << a[i] << " ";
cout << endl;
return 0;
}
B - Between B and B
Problem Statement
You are given a sequence
(
X
1
,
X
2
,
…
,
X
M
)
(X_1, X_2, \dots, X_M)
(X1,X2,…,XM) of length
M
M
M consisting of integers between
1
1
1 and
M
M
M, inclusive.
Find the number, modulo
998244353
998244353
998244353, of sequences
A
=
(
A
1
,
A
2
,
…
,
A
N
)
A = (A_1, A_2, \dots, A_N)
A=(A1,A2,…,AN) of length
N
N
N consisting of integers between
1
1
1 and
M
M
M, inclusive, that satisfy the following condition:
For each
B
=
1
,
2
,
…
,
M
B = 1, 2, \dots, M
B=1,2,…,M, the value
X
B
X_B
XB exists between any two different occurrences of
B
B
B in
A
A
A (including both ends).
More formally, for each
B
=
1
,
2
,
…
,
M
B = 1, 2, \dots, M
B=1,2,…,M, the following condition must hold:
For every pair of integers
(
l
,
r
)
(l, r)
(l,r) such that KaTeX parse error: Expected 'EOF', got '&' at position 10: 1 \leq l &̲lt; r \leq N and
A
l
=
A
r
=
B
A_l = A_r = B
Al=Ar=B, there exists an integer
m
m
m (
l
≤
m
≤
r
l \leq m \leq r
l≤m≤r) such that
A
m
=
X
B
A_m = X_B
Am=XB.
Constraints
1
≤
M
≤
10
1 \leq M \leq 10
1≤M≤10
1
≤
N
≤
1
0
4
1 \leq N \leq 10^4
1≤N≤104
1
≤
X
i
≤
M
1 \leq X_i \leq M
1≤Xi≤M
All input values are integers.
Input
The input is given from Standard Input in the following format:
M
M
M
N
N
N
X
1
X_1
X1
X
2
X_2
X2
⋯
\cdots
⋯
X
M
X_M
XM
Output
Print the answer.
Sample Input 1
3 4
2 1 2
Sample Output 1
14
Here are examples of sequences
A
A
A that satisfy the condition:
(
1
,
3
,
2
,
3
)
(1, 3, 2, 3)
(1,3,2,3)
(
2
,
1
,
2
,
1
)
(2, 1, 2, 1)
(2,1,2,1)
(
3
,
2
,
1
,
3
)
(3, 2, 1, 3)
(3,2,1,3)
Here are non-examples:
(
1
,
3
,
1
,
3
)
(1, 3, 1, 3)
(1,3,1,3)
There is no
X
3
=
2
X_3 = 2
X3=2 between the
3
3
3s.
(
2
,
2
,
1
,
3
)
(2, 2, 1, 3)
(2,2,1,3)
There is no
X
2
=
1
X_2 = 1
X2=1 between the
2
2
2s.
Sample Input 2
4 8
1 2 3 4
Sample Output 2
65536
All sequences of length
8
8
8 consisting of integers between
1
1
1 and
4
4
4 satisfy the condition.
Note that when
X
B
=
B
X_B = B
XB=B, there is always a
B
B
B between two different occurrences of
B
B
B.
Sample Input 3
4 9
2 3 4 1
Sample Output 3
628
Solution
具体见文末视频。
Code
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e4 + 10, M = 11, mod = 998244353;
int n, m;
int a[M], f[N][1 << M], mask[M];
signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> m >> n;
for (int i = 1; i <= m; i ++)
cin >> a[i], mask[a[i]] |= 1ll << i - 1;
f[0][(1 << m) - 1] = 1;
for (int i = 0; i < n; i ++)
for (int j = 1; j <= m; j ++)
for (int k = 0; k < 1 << m; k ++)
if ((k >> j - 1) & 1)
f[i + 1][(k ^ (1 << j - 1)) | mask[j]] = (f[i + 1][(k ^ (1 << j - 1)) | mask[j]] + f[i][k]) % mod;
int res = 0;
for (int i = 0; i < 1 << m; i ++)
res = (res + f[n][i]) % mod;
cout << res << endl;
return 0;
}
C - Beware of Overflow
Problem Statement
This is an interactive problem (where your program interacts with the judge via input and output).
You are given a positive integer
N
N
N.
The judge has a hidden positive integer
R
R
R and
N
N
N integers
A
1
,
A
2
,
…
,
A
N
A_1, A_2, \dots, A_N
A1,A2,…,AN. It is guaranteed that
∣
A
i
∣
≤
R
|A_i|\le R
∣Ai∣≤R and
∣
∑
i
=
1
N
A
i
∣
≤
R
\left|\displaystyle\sum_{i=1}^{N}A_i\right| \le R
i=1∑NAi
≤R.
There is a blackboard on which you can write integers with absolute values not exceeding
R
R
R. Initially, the blackboard is empty.
The judge has written the values
A
1
,
A
2
,
…
,
A
N
A_1, A_2, \dots, A_N
A1,A2,…,AN on the blackboard in this order. Your task is to make the blackboard contain only one value
∑
i
=
1
N
A
i
\displaystyle\sum_{i=1}^{N}A_i
i=1∑NAi.
You cannot learn the values of
R
R
R and
A
i
A_i
Ai directly, but you can interact with the judge up to
25000
25000
25000 times.
For a positive integer
i
i
i, let
X
i
X_i
Xi be the
i
i
i-th integer written on the blackboard. Specifically,
X
i
=
A
i
X_i = A_i
Xi=Ai for
i
=
1
,
2
,
…
,
N
i=1,2,\dots,N
i=1,2,…,N.
In one interaction, you can specify two distinct positive integers
i
i
i and
j
j
j and choose one of the following actions:
Perform addition. The judge will erase
X
i
X_i
Xi and
X
j
X_j
Xj from the blackboard and write
X
i
+
X
j
X_i + X_j
Xi+Xj on the blackboard.
∣
X
i
+
X
j
∣
≤
R
|X_i + X_j| \leq R
∣Xi+Xj∣≤R must hold.
Perform comparison. The judge will tell you whether KaTeX parse error: Expected 'EOF', got '&' at position 5: X_i &̲lt; X_j is true or false.
Here, at the beginning of each interaction, the
i
i
i-th and
j
j
j-th integers written on the blackboard must not have been erased.
Perform the interactions appropriately so that after all interactions, the blackboard contains only one value
∑
i
=
1
N
A
i
\displaystyle\sum_{i=1}^{N}A_i
i=1∑NAi.
The values of
R
R
R and
A
i
A_i
Ai are determined before the start of the conversation between your program and the judge.
Constraints
2
≤
N
≤
1000
2 \leq N \leq 1000
2≤N≤1000
1
≤
R
≤
1
0
9
1 \leq R \leq 10^9
1≤R≤109
∣
A
i
∣
≤
R
|A_i| \leq R
∣Ai∣≤R
∣
∑
i
=
1
N
A
i
∣
≤
R
\left|\displaystyle\sum_{i=1}^{N}A_i\right| \le R
i=1∑NAi
≤R
N
N
N,
R
R
R, and
A
i
A_i
Ai are integers.
Input and Output
This is an interactive problem (where your program interacts with the judge via input and output).
First, read
N
N
N from Standard Input.
N N N
Next, repeat the interactions until the blackboard contains only one value
∑
i
=
1
N
A
i
\displaystyle\sum_{i=1}^{N}A_i
i=1∑NAi.
When performing addition, make an output in the following format to Standard Output. Append a newline at the end. Here,
i
i
i and
j
j
j are distinct positive integers.
- i i i j j j
The response from the judge will be given from Standard Input in the following format:
P P P
Here,
P
P
P is an integer:
If
P
≥
N
+
1
P \geq N + 1
P≥N+1, it means that the value
X
i
+
X
j
X_i + X_j
Xi+Xj has been written on the blackboard, and it is the
P
P
P-th integer written.
If
P
=
−
1
P = -1
P=−1, it means that
i
i
i and
j
j
j do not satisfy the constraints, or the number of interactions has exceeded
25000
25000
25000.
When performing comparison, make an output in the following format to Standard Output. Append a newline at the end. Here,
i
i
i and
j
j
j are distinct positive integers.
? i i i j j j
The response from the judge will be given from Standard Input in the following format:
Q Q Q
Here,
Q
Q
Q is an integer:
If
Q
=
1
Q = 1
Q=1, it means that KaTeX parse error: Expected 'EOF', got '&' at position 5: X_i &̲lt; X_j is true.
If
Q
=
0
Q = 0
Q=0, it means that KaTeX parse error: Expected 'EOF', got '&' at position 5: X_i &̲lt; X_j is false.
If
Q
=
−
1
Q = -1
Q=−1, it means that
i
i
i and
j
j
j do not satisfy the constraints, or the number of interactions has exceeded
25000
25000
25000.
For both types of interactions, if the judge’s response is
−
1
-1
−1, your program is already considered incorrect. In this case, terminate your program immediately.
When the blackboard contains only one value
∑
i
=
1
N
A
i
\displaystyle\sum_{i=1}^{N}A_i
i=1∑NAi, report this to the judge in the following format. This does not count towards the number of interactions. Then, terminate your program immediately.
!
If you make an output in a format that does not match any of the above, -1
will be given from Standard Input.
-1
In this case, your program is already considered incorrect. Terminate your program immediately.
Notes
For each output, append a newline at the end and flush Standard Output. Otherwise, the verdict may be TLE.
Terminate your program immediately after outputting the result (or receiving -1
). Otherwise, the verdict will be indeterminate.
Extra newlines will be considered as malformed output.
Sample Input and Output
Here is a possible conversation with N = 3 , R = 10 , A 1 = − 1 , A 2 = 10 , A 3 = 1 N=3, R=10, A_1=-1, A_2=10, A_3=1 N=3,R=10,A1=−1,A2=10,A3=1.
Input | Output | Explanation |
---|---|---|
3 | First, the integer $N$ is given. | |
? 1 2 | Perform a comparison. | |
1 | The judge returns $1$ because $X_1\lt X_2\ (-1\lt 10)$. | |
+ 1 3 | Perform an addition. | |
4 | The judge erases $X_1 = -1$ and $X_3 = 1$ from the blackboard and writes $X_1 + X_3 = 0$. This is the fourth integer written. | |
+ 2 4 | Perform an addition. | |
5 | The judge erases $X_2 = 10$ and $X_4 = 0$ from the blackboard and writes $X_2 + X_4 = 10$. This is the fifth integer written. | |
! | The blackboard contains only one value $\displaystyle\sum_{i=1}^{N}A_i$, so report this to the judge. |
Solution
具体见文末视频。
Code
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
bool cmp(int a, int b) {
cout << "? " << a << " " << b << endl;
int ok;
cin >> ok;
return ok;
}
signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n;
cin >> n;
std::vector<int> id;
for (int i = 1; i <= n; i ++)
id.push_back(i);
sort(id.begin(), id.end(), cmp);
while (n > 1) {
cout << "+ " << id[0] << " " << id.back() << endl;
int p;
cin >> p;
id.erase(id.begin()), id.pop_back();
n --;
if (n == 1) break;
int l = 0, r = id.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (cmp(p, id[mid])) r = mid;
else l = mid + 1;
}
if (!cmp(p, id[r])) r ++;
id.insert(id.begin() + r, p);
}
cout << "!\n";
return 0;
}
视频题解
AtCoder Regular Contest 179(A ~ C 题讲解)
最后祝大家早日