Thanks for your participation! I am so sorry for my careless review. We were preparing for this round for many months and made some problems which writers and testers are all like. We do want to give everyone a gold time to enjoy the contest. But carelessness is deadly. In problem B, some test cases should have been made, but we missed them in not only the pretests but also the final tests. In fact, we had not noticed it until some suspicious hacks appeared. I and all co-authors sincerely regret our mistake and hope you can forgive us.↵
↵
Besides, few people are cyberbullying authors, please do not do so. If you have a bad experience, you can downvote me because of our fault.↵
↵
[problem:1774A] ↵
Idea: [user:cirno_9baka,2022-12-17]↵
↵
<spoiler summary="Solution">↵
The answer is the number of $1$s modulo $2$.↵
↵
We can get that by adding '-' before the $\text{2nd}, \text{4th}, \cdots, 2k\text{-th}$ $1$, and '+' before the $\text{3rd}, \text{5th}, \cdots, 2k+1\text{-th}$ $1$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
char c[1005];↵
int main() {↵
int t;↵
scanf("%d", &t);↵
int n;↵
while (t--) {↵
scanf("%d", &n);↵
scanf("%s", c + 1);↵
int u = 0;↵
for (int i = 1; i <= n; ++i) {↵
bool fl = (c[i] == '1') && u;↵
u ^= (c[i] - '0');↵
if (i != 1) putchar(fl ? '-' : '+');↵
}↵
putchar('\n');↵
}↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
[problem:1774B] ↵
Idea: [user:cirno_9baka,2022-12-17]↵
↵
<spoiler summary="Solution">↵
First, We can divide $n$ cells into $\left\lceil\frac{n}{k}\right\rceil$ segments that except the last segment, all segments have length $k$. Then in each segment, the colors in it are pairwise different. It's easy to find any $a_i$ should be smaller than or equal to $\left\lceil\frac{n}{k}\right\rceil$.↵
↵
Then we can count the number of $a_i$ which is equal to $\left\lceil\frac{n}{k}\right\rceil$. This number must be smaller than or equal to $n \bmod k$, which is the length of the last segment.↵
↵
All $a$ that satisfies the conditions above is valid. We can construct a coloring using the method below:↵
↵
First, we pick out all colors $i$ that $a_i=\left\lceil\frac{n}{k}\right\rceil$, then we use color $i$ to color the $j$-th cell in each segment.↵
↵
Then we pick out all colors $i$ that $a_i<\left\lceil\frac{n}{k}\right\rceil-1$ and use these colors to color the rest of cells with cyclic order(i.e. color $j$-th cell of the first segment, of second the segment ... of the $\left\lceil\frac{n}{k}\right\rceil$ segment, and let $j++$. when one color is used up, we begin to use the next color)↵
↵
At last, we pick out all colors $i$ that $a_i=\left\lceil\frac{n}{k}\right\rceil-1$, and color them with the cyclic order.↵
↵
This method will always give a valid construction.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
int t;↵
scanf("%d", &t);↵
while (t--) {↵
int n, m, k;↵
scanf("%d %d %d", &n, &m, &k);↵
int fl = 0;↵
for (int i = 1; i <= m; ++i) {↵
int a;↵
scanf("%d", &a);↵
if (a == (n + k - 1) / k) ++fl;↵
if (a > (n + k - 1) / k) fl = 1 << 30;↵
}↵
puts(fl <= (n - 1) % k + 1 ? "YES" : "NO");↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1774C] ↵
Idea: [user:little09,2022-12-17]↵
↵
<spoiler summary="Solution">↵
We define $f_i$ to mean that the maximum $x$ satisfies $s_{i-x+1}=s_{i-x+2}=...=s_{i}$.↵
↵
It can be proved that for $x$ players, $f_{x-1}$ players are bound to lose and the rest have a chance to win. So the answer to the first $i$ battles is $ans_i=i-f_i+1$.↵
↵
Next, we prove this conclusion. Suppose there are $n$ players and $n-1$ battles, and $s_{n-1}=1$, and there are $x$ consecutive $1$ at the end. If $x=n-1$, then obviously only the $n$-th player can win. Otherwise, $s_{n-1-x}$ must be 0. Consider the following facts:↵
↵
1. Players $1$ to $x$ have no chance to win. If the player $i$ ($1\le i\le x$) can win, he must defeat the player whose temperature value is lower than him in the last $x$ battles. However, in total, only the $i-1$ player's temperature value is lower than his. Because $i-1<x$, the $i$-th player cannot win.↵
↵
2. Players from $x+1$ to $n$ have a chance to win. For the player $i$ ($x+1\le i\le n$), we can construct: in the first $n-2-x$ battles, we let all players whose temperature value in $[x+1,n]$ except the player $i$ fight so that only one player will remain. In the $(n-1-x)$-th battle, we let the remaining player fight with the player $1$. Since $s_{n-1-x}=0$, the player $1$ will win. Then there are only the first $x$ players and the player $i$ in the remaining $x$ battles, so the player $i$ can win.↵
↵
For $s_{n-1}=0$, the situation is similar and it will not be repeated here.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int N = 300005;↵
int T, n, ps[2];↵
char a[N];↵
↵
void solve() {↵
scanf("%d %s", &n, a + 1);↵
ps[0] = ps[1] = 0;↵
for (int i = 1; i < n; ++i) {↵
ps[a[i] - 48] = i;↵
if (a[i] == '0')↵
printf("%d ", ps[1] + 1);↵
else↵
printf("%d ", ps[0] + 1);↵
}↵
putchar('\n');↵
}↵
int main() {↵
scanf("%d", &T);↵
while (T--) solve();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1774D] ↵
Idea: [user:mejiamejia,2022-12-17] and [user:AquaMoon,2022-12-17]↵
↵
<spoiler summary="Solution">↵
Considering that we need to make the number of $1$s in each array the same, we should calculate the sum of $1$s, and every array has $\frac{sum}{n}$ $1$s. Because only the same position of two different arrays can be selected for exchange each time, for a position $pos$ , we traverse each array each time. If the number of $1$s in this array is not enough, then we need to turn some $0$s into $1$s; If the number of $1$s in this array is more than we need, then some $1$s should be turned into $0$s. It can be proved that as long as the total number of $1$s is a multiple of n, the number of $1$s in each array can be made the same through exchange.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
int main() {↵
int T;↵
scanf("%d", &T);↵
while (T--) {↵
int n, m;↵
scanf("%d %d", &n, &m);↵
std::vector<std::vector<int>> A(n, std::vector<int>(m, 0));↵
std::vector<int> sum(n, 0);↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < m; ++j) {↵
scanf("%d", &A[i][j]);↵
sum[i] += A[i][j];↵
}↵
}↵
int tot = 0;↵
for (int i = 0; i < n; ++i) tot += sum[i];↵
if (tot % n) {↵
puts("-1");↵
continue;↵
}↵
tot /= n;↵
std::vector<std::tuple<int, int, int>> ans;↵
std::vector<int> Vg, Vl;↵
Vg.reserve(n), Vl.reserve(n);↵
for (int j = 0; j < m; ++j) {↵
for (int i = 0; i < n; ++i) {↵
if (sum[i] > tot && A[i][j]) Vg.push_back(i);↵
if (sum[i] < tot && !A[i][j]) Vl.push_back(i);↵
}↵
for (int i = 0; i < (int)std::min(Vl.size(), Vg.size()); ++i) {↵
++sum[Vl[i]], --sum[Vg[i]];↵
ans.emplace_back(Vl[i], Vg[i], j);↵
}↵
Vl.clear(), Vg.clear();↵
}↵
printf("%d\n", (int)ans.size());↵
for (auto [i, j, k] : ans) printf("%d %d %d\n", i + 1, j + 1, k + 1);↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1774E] ↵
Idea: [user:cirno_9baka,2022-12-17]↵
↵
<spoiler summary="Solution">↵
We can find that for any $d$-th ancestor of some $b_i$, the first piece must pass it some time. Otherwise, we will violate the distance limit. The second piece must pass the $d$-th ancestor of each $b_i$ as well. Then we can add the $d$-th ancestor of each $a_i$ to the array $b$, and add the $d$-th ancestor of each $b_i$ to the array $a$.↵
↵
Then we can find now we can find a solution that each piece only needs to visit its nodes using the shortest route, without considering the limit of $d$, and the total length can be easily computed. We can find that if we adopt the strategy that we visit these nodes according to their DFS order(we merge the array of $a$ and $b$, and sort them according to the DFS order, if the first one is from $a$, we try to move the first piece to this position, otherwise use the second piece), and move the other piece one step closer to the present piece only if the next step of the present piece will violate the distance limit, then we can ensure the movement exactly just let each piece visit its necessary node without extra operations.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int N = 1e6 + 5;↵
int t[N * 2], nxt[N * 2], cnt, h[N];↵
int n, d;↵
void add(int x, int y) {↵
t[++cnt] = y;↵
nxt[cnt] = h[x];↵
h[x] = cnt;↵
}↵
int a[N], b[N];↵
bool f[2][N];↵
void dfs1(int x, int fa, int dis) {↵
a[dis] = x;↵
if (dis > d)↵
b[x] = a[dis - d];↵
else↵
b[x] = 1;↵
for (int i = h[x]; i; i = nxt[i]) {↵
if (t[i] == fa) continue;↵
dfs1(t[i], x, dis + 1);↵
}↵
}↵
void dfs2(int x, int fa, int tp) {↵
bool u = 0;↵
for (int i = h[x]; i; i = nxt[i]) {↵
if (t[i] == fa) continue;↵
dfs2(t[i], x, tp);↵
u |= f[tp][t[i]];↵
}↵
f[tp][x] |= u;↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
cin >> n >> d;↵
for (int i = 1; i < n; i++) {↵
int x, y;↵
cin >> x >> y;↵
add(x, y), add(y, x);↵
}↵
dfs1(1, 0, 1);↵
for (int i = 0; i <= 1; i++) {↵
int num;↵
cin >> num;↵
for (int j = 1; j <= num; j++) {↵
int x;↵
cin >> x;↵
f[i][x] = 1, f[i ^ 1][b[x]] = 1;↵
}↵
}↵
for (int i = 0; i <= 1; i++) dfs2(1, 0, i);↵
int ans = 0;↵
for (int i = 0; i <= 1; i++)↵
for (int j = 2; j <= n; j++)↵
if (f[i][j]) ans += 2;↵
cout << ans;↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1774F1] ↵
Idea: [user:little09,2022-12-17]↵
↵
<spoiler summary="Solution">↵
Let $X=\max x$.↵
↵
Think about what ‘Repeat’ is doing. Assuming the total damage is $tot$ ($tot$ is easy to calculate because it will be multiplied by $2$ after each ‘Repeat’ and be added after each ‘Attack’). After repeating, each pig with a current HP of $w$ ($w > tot$) will clone a pig with a HP of $w-tot$.↵
↵
Why? ‘Repeat’ will do what you just did again, so each original pig will certainly create a pig the same as it, and it will be attacked by $tot$, so it can be considered that a pig with $w-tot$ HP has been cloned.↵
↵
Next, the problem is to maintain a multiset $S$, which supports: adding a number, subtracting $x$ for all numbers, and inserting each number after subtracting $tot$. Find the number of positive elements in the final multiset.↵
↵
$tot$ in ‘Repeat’ after the first ‘Attack’ will multiply by $2$ every time, so it will exceed $X$ in $O(\log X)$ times. That is, only $O(\log X)$ ‘Repeat’ operations are effective. So we can maintain $S$ in brute force. Every time we do ‘Repeat’, we take out all the numbers larger than $tot$, then subtract and insert them again. Note that we may do some ‘Repeat’ operations when $tot=0$, which will result in the number of pigs generated before multiplying by $2$. Therefore, we also need to maintain the total multiplication.↵
↵
If you use map to maintain it, the time complexity is $O((n+X)\log ^2X)$. It can pass F1. You can also use some ways to make the time complexity $O((n+X)\log X)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
// Author: Little09↵
// Problem: F. Magician and Pigs (Easy Version)↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define ll long long↵
const ll mod = 998244353, inv = (mod + 1) / 2;↵
int n;↵
map<ll, ll> s;↵
ll tot, mul = 1, ts = 1;↵
inline void add(ll &x, ll y) { (x += y) >= mod && (x -= mod); }↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
cin >> n;↵
while (n--) {↵
int op;↵
cin >> op;↵
if (op == 1) {↵
ll x;↵
cin >> x;↵
add(s[x + tot], ts);↵
} else if (op == 2) {↵
ll x;↵
cin >> x;↵
tot += x;↵
} else if (tot <= 2e5) {↵
if (tot == 0)↵
mul = mul * 2 % mod, ts = ts * inv % mod;↵
else {↵
for (ll i = tot + 2e5; i > tot; i--) add(s[i + tot], s[i]);↵
tot *= 2;↵
}↵
}↵
}↵
ll res = 0;↵
for (auto i : s)↵
if (i.first > tot) add(res, i.second);↵
res = res * mul % mod;↵
cout << res;↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1774F2] ↵
Idea: [user:little09,2022-12-17]↵
↵
<spoiler summary="Solution">↵
For F1, there is another way. Consider every pig. When ``Repeat``, it will clone, and when ``Attack``, all its clones will be attacked together. Therefore, considering all the operations behind each pig, you can choose to reduce $x$ (the current total damage) or not when ``Repeat``, and you must choose to reduce $x$ when ``Attack``. Any final choice will become a pig (living or not).↵
↵
We just need to calculate how many ``Repeat`` choices can make a living pig. For ``Repeat`` of $x=0$, there is no difference between the two choices. For the ``Repeat`` of $x\geq 2\times 10^5$, it is obvious that you can only choose not to reduce $x$. Except for the above parts, there are only $O(\log x)$ choices. You can just find a subset or use knapsack to solve it. It can also pass F1 and the time complexity is $O((n+X)\log X)$.↵
↵
The bottleneck of using this method to do F2 lies in the backpack. The problem is that we need to find how many subsets whose sum $<x$ of of a set whose size is $O(\log X)$.↵
↵
Observation: if you sort the set, each element is greater than the sum of all elements smaller than it. We can use observation to solve the problem. Consider each element from large to small. Suppose you now need to find elements and subsets of $<x$. If the current element $\ge x$, it must not be selected; If the current element $<x$, if it is not selected, the following elements can be selected at will (the sum of all the following elements is less than it). It can be recursive. Thus, for a given $x$, we can find the number of subsets whose sum $<x$ within $O(\log X)$.↵
↵
The time complexity is $O(n\log X)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
// Author: Little09↵
// Problem: F. Magician and Pigs↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define ll long long↵
#define mem(x) memset(x, 0, sizeof(x))↵
#define endl "\n"↵
#define printYes cout << "Yes\n"↵
#define printYES cout << "YES\n"↵
#define printNo cout << "No\n"↵
#define printNO cout << "NO\n"↵
#define lowbit(x) ((x) & (-(x)))↵
#define pb push_back↵
#define mp make_pair↵
#define pii pair<int, int>↵
#define fi first↵
#define se second↵
↵
const ll inf = 1000000000000000000;↵
// const ll inf=1000000000;↵
const ll mod = 998244353;↵
// const ll mod=1000000007;↵
↵
const int N = 800005;↵
int n, m;↵
ll a[N], b[N], c[N], cnt, s[N], d[N], cntd;↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
cin >> n;↵
ll maxs = 1e9, sum = 0;↵
for (int i = 1; i <= n; i++) {↵
cin >> a[i];↵
if (a[i] != 3) cin >> b[i];↵
if (a[i] == 2) sum += b[i];↵
sum = min(sum, maxs);↵
if (a[i] == 3) b[i] = sum, sum = sum * 2;↵
sum = min(sum, maxs);↵
}↵
sum = 0;↵
ll res = 1, ans = 0;↵
for (int i = n; i >= 1; i--) {↵
if (a[i] == 2)↵
sum += b[i];↵
else if (a[i] == 3) {↵
if (b[i] == maxs) continue;↵
if (b[i] == 0) {↵
res = res * 2 % mod;↵
continue;↵
}↵
c[++cnt] = b[i];↵
} else {↵
b[i] -= sum;↵
if (b[i] <= 0) continue;↵
ll su = 0, r = b[i];↵
for (int j = 1; j <= cnt; j++) {↵
if (r > c[j]) {↵
su = (su + (1ll << (cnt - j))) % mod;↵
r -= c[j];↵
}↵
}↵
su = (su + 1) % mod;↵
ans = (ans + su * res) % mod;↵
}↵
}↵
cout << ans;↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1774G] ↵
Idea: [user:ChthollyNotaSeniorious,2022-12-17] and [user:DataStructures,2022-12-17]↵
↵
<spoiler summary="Hint 1">↵
If there exist two segments $(l_1, r_1), (l_2, r_2)$ such that $l_1 \le l_2 \le r_2 \le r_1$ and we choose $(l_1, r_1)$, number of ways of choosing $(l_2, r_2)$ at the same time will be equal to that of not choosing. Hence if we choose $(l_1, r_1)$, the signed number of ways will be $0$. So we can delete $(l_1, r_1)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
It can be proved that the absolute value of every $f_{l,r} - g_{l,r}$ doesn't exceed $1$.↵
↵
Proof: First, find segments $(l_i, r_i)$ which are completely contained by $(l, r)$.↵
↵
Let us sort $(l_i, r_i)$ in ascending order of $l_i$. As there does not exist a segment that contains another, $r_i$ are also sorted.↵
↵
Assume that $l_2 < l_3 \leq r_1$ and $r_3 \geq r_2$. If we choose segments $1$ and $3$, choosing $2$ or not will be the same except for the sign. So $3$ is useless. So we can delete such useless segments. After the process, $l_3 > r_1, l_4 > r_2, \cdots$ will be held. If $[l_1, r_1] \cup [l_2, r_2] \cup \cdots \cup [l_k, r_k] = [l, r]$, answer will be $(-1)^k$, else answer will be $0$.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
This picture shows what the segments eventually are like:↵
↵
↵
↵
For $[l_i, r_i]$, we can find the lowest $j$ such that $l_j > r_j$ and construct a tree by linking such $i$ and $j$. Then the LCA of $1$ and $2$ will be $5$, where the answer becomes 0.↵
↵
So we can get the answer quickly by simply finding the LCA of two segments.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#define File(a) freopen(a ".in", "r", stdin), freopen(a ".out", "w", stdout)↵
↵
using tp = std::tuple<int, int, int>;↵
const int sgn[] = {1, 998244352};↵
const int N = 200005;↵
↵
int x[N], y[N];↵
std::vector<tp> V;↵
bool del[N];↵
int fa[20][N];↵
int m, q;↵
↵
int main() {↵
scanf("%d %d", &m, &q);↵
for (int i = 1; i <= m; ++i)↵
scanf("%d %d", x + i, y + i), V.emplace_back(y[i], -x[i], i);↵
std::sort(V.begin(), V.end());↵
int mxl = 0;↵
for (auto [y, x, i] : V) {↵
if (-x <= mxl) del[i] = true;↵
mxl = std::max(mxl, -x);↵
}↵
V.clear();↵
x[m + 1] = y[m + 1] = 1e9 + 1;↵
for (int i = 1; i <= m + 1; ++i) {↵
if (!del[i]) V.emplace_back(x[i], y[i], i);↵
}↵
std::sort(V.begin(), V.end());↵
for (auto [x, y, id] : V) {↵
int t = std::get<2>(*std::lower_bound(V.begin(), V.end(), tp{y + 1, 0, 0}));↵
fa[0][id] = t;↵
}↵
fa[0][m + 1] = m + 1;↵
for (int k = 1; k <= 17; ++k) {↵
for (int i = 1; i <= m + 1; ++i) fa[k][i] = fa[k - 1][fa[k - 1][i]];↵
}↵
for (int i = 1; i <= q; ++i) {↵
int l, r;↵
scanf("%d %d", &l, &r);↵
int u = std::lower_bound(V.begin(), V.end(), tp{l, 0, 0}) - V.begin(), v = u + 1;↵
u = std::get<2>(V[u]);↵
if (x[u] != l || y[u] > r) {↵
puts("0");↵
continue;↵
}↵
if (y[u] == r) {↵
puts("998244352");↵
continue;↵
}↵
v = std::get<2>(V[v]);↵
if (y[v] > r || x[v] > y[u]) {↵
puts("0");↵
continue;↵
}↵
int numu = 0, numv = 0;↵
for (int i = 17; i >= 0; --i) {↵
if (y[fa[i][u]] <= r) {↵
u = fa[i][u];↵
numu += !i;↵
}↵
}↵
for (int i = 17; i >= 0; --i) {↵
if (y[fa[i][v]] <= r) {↵
v = fa[i][v];↵
numv += !i;↵
}↵
}↵
if (u == v || (y[u] != r && y[v] != r))↵
puts("0");↵
else↵
printf("%d\n", sgn[numu ^ numv]);↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1774H] ↵
Idea: [user:Ecrade_,2022-12-17]↵
↵
To be added...
↵
Besides, few people are cyberbullying authors, please do not do so. If you have a bad experience, you can downvote me because of our fault.↵
↵
[problem:1774A] ↵
Idea: [user:cirno_9baka,2022-12-17]↵
↵
<spoiler summary="Solution">↵
The answer is the number of $1$s modulo $2$.↵
↵
We can get that by adding '-' before the $\text{2nd}, \text{4th}, \cdots, 2k\text{-th}$ $1$, and '+' before the $\text{3rd}, \text{5th}, \cdots, 2k+1\text{-th}$ $1$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
char c[1005];↵
int main() {↵
int t;↵
scanf("%d", &t);↵
int n;↵
while (t--) {↵
scanf("%d", &n);↵
scanf("%s", c + 1);↵
int u = 0;↵
for (int i = 1; i <= n; ++i) {↵
bool fl = (c[i] == '1') && u;↵
u ^= (c[i] - '0');↵
if (i != 1) putchar(fl ? '-' : '+');↵
}↵
putchar('\n');↵
}↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
[problem:1774B] ↵
Idea: [user:cirno_9baka,2022-12-17]↵
↵
<spoiler summary="Solution">↵
First, We can divide $n$ cells into $\left\lceil\frac{n}{k}\right\rceil$ segments that except the last segment, all segments have length $k$. Then in each segment, the colors in it are pairwise different. It's easy to find any $a_i$ should be smaller than or equal to $\left\lceil\frac{n}{k}\right\rceil$.↵
↵
Then we can count the number of $a_i$ which is equal to $\left\lceil\frac{n}{k}\right\rceil$. This number must be smaller than or equal to $n \bmod k$, which is the length of the last segment.↵
↵
All $a$ that satisfies the conditions above is valid. We can construct a coloring using the method below:↵
↵
First, we pick out all colors $i$ that $a_i=\left\lceil\frac{n}{k}\right\rceil$, then we use color $i$ to color the $j$-th cell in each segment.↵
↵
Then we pick out all colors $i$ that $a_i<\left\lceil\frac{n}{k}\right\rceil-1$ and use these colors to color the rest of cells with cyclic order(i.e. color $j$-th cell of the first segment, of second the segment ... of the $\left\lceil\frac{n}{k}\right\rceil$ segment, and let $j++$. when one color is used up, we begin to use the next color)↵
↵
At last, we pick out all colors $i$ that $a_i=\left\lceil\frac{n}{k}\right\rceil-1$, and color them with the cyclic order.↵
↵
This method will always give a valid construction.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
int t;↵
scanf("%d", &t);↵
while (t--) {↵
int n, m, k;↵
scanf("%d %d %d", &n, &m, &k);↵
int fl = 0;↵
for (int i = 1; i <= m; ++i) {↵
int a;↵
scanf("%d", &a);↵
if (a == (n + k - 1) / k) ++fl;↵
if (a > (n + k - 1) / k) fl = 1 << 30;↵
}↵
puts(fl <= (n - 1) % k + 1 ? "YES" : "NO");↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1774C] ↵
Idea: [user:little09,2022-12-17]↵
↵
<spoiler summary="Solution">↵
We define $f_i$ to mean that the maximum $x$ satisfies $s_{i-x+1}=s_{i-x+2}=...=s_{i}$.↵
↵
It can be proved that for $x$ players, $f_{x-1}$ players are bound to lose and the rest have a chance to win. So the answer to the first $i$ battles is $ans_i=i-f_i+1$.↵
↵
Next, we prove this conclusion. Suppose there are $n$ players and $n-1$ battles, and $s_{n-1}=1$, and there are $x$ consecutive $1$ at the end. If $x=n-1$, then obviously only the $n$-th player can win. Otherwise, $s_{n-1-x}$ must be 0. Consider the following facts:↵
↵
1. Players $1$ to $x$ have no chance to win. If the player $i$ ($1\le i\le x$) can win, he must defeat the player whose temperature value is lower than him in the last $x$ battles. However, in total, only the $i-1$ player's temperature value is lower than his. Because $i-1<x$, the $i$-th player cannot win.↵
↵
2. Players from $x+1$ to $n$ have a chance to win. For the player $i$ ($x+1\le i\le n$), we can construct: in the first $n-2-x$ battles, we let all players whose temperature value in $[x+1,n]$ except the player $i$ fight so that only one player will remain. In the $(n-1-x)$-th battle, we let the remaining player fight with the player $1$. Since $s_{n-1-x}=0$, the player $1$ will win. Then there are only the first $x$ players and the player $i$ in the remaining $x$ battles, so the player $i$ can win.↵
↵
For $s_{n-1}=0$, the situation is similar and it will not be repeated here.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int N = 300005;↵
int T, n, ps[2];↵
char a[N];↵
↵
void solve() {↵
scanf("%d %s", &n, a + 1);↵
ps[0] = ps[1] = 0;↵
for (int i = 1; i < n; ++i) {↵
ps[a[i] - 48] = i;↵
if (a[i] == '0')↵
printf("%d ", ps[1] + 1);↵
else↵
printf("%d ", ps[0] + 1);↵
}↵
putchar('\n');↵
}↵
int main() {↵
scanf("%d", &T);↵
while (T--) solve();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1774D] ↵
Idea: [user:mejiamejia,2022-12-17] and [user:AquaMoon,2022-12-17]↵
↵
<spoiler summary="Solution">↵
Considering that we need to make the number of $1$s in each array the same, we should calculate the sum of $1$s, and every array has $\frac{sum}{n}$ $1$s. Because only the same position of two different arrays can be selected for exchange each time, for a position $pos$ , we traverse each array each time. If the number of $1$s in this array is not enough, then we need to turn some $0$s into $1$s; If the number of $1$s in this array is more than we need, then some $1$s should be turned into $0$s. It can be proved that as long as the total number of $1$s is a multiple of n, the number of $1$s in each array can be made the same through exchange.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
int main() {↵
int T;↵
scanf("%d", &T);↵
while (T--) {↵
int n, m;↵
scanf("%d %d", &n, &m);↵
std::vector<std::vector<int>> A(n, std::vector<int>(m, 0));↵
std::vector<int> sum(n, 0);↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < m; ++j) {↵
scanf("%d", &A[i][j]);↵
sum[i] += A[i][j];↵
}↵
}↵
int tot = 0;↵
for (int i = 0; i < n; ++i) tot += sum[i];↵
if (tot % n) {↵
puts("-1");↵
continue;↵
}↵
tot /= n;↵
std::vector<std::tuple<int, int, int>> ans;↵
std::vector<int> Vg, Vl;↵
Vg.reserve(n), Vl.reserve(n);↵
for (int j = 0; j < m; ++j) {↵
for (int i = 0; i < n; ++i) {↵
if (sum[i] > tot && A[i][j]) Vg.push_back(i);↵
if (sum[i] < tot && !A[i][j]) Vl.push_back(i);↵
}↵
for (int i = 0; i < (int)std::min(Vl.size(), Vg.size()); ++i) {↵
++sum[Vl[i]], --sum[Vg[i]];↵
ans.emplace_back(Vl[i], Vg[i], j);↵
}↵
Vl.clear(), Vg.clear();↵
}↵
printf("%d\n", (int)ans.size());↵
for (auto [i, j, k] : ans) printf("%d %d %d\n", i + 1, j + 1, k + 1);↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1774E] ↵
Idea: [user:cirno_9baka,2022-12-17]↵
↵
<spoiler summary="Solution">↵
We can find that for any $d$-th ancestor of some $b_i$, the first piece must pass it some time. Otherwise, we will violate the distance limit. The second piece must pass the $d$-th ancestor of each $b_i$ as well. Then we can add the $d$-th ancestor of each $a_i$ to the array $b$, and add the $d$-th ancestor of each $b_i$ to the array $a$.↵
↵
Then we can find now we can find a solution that each piece only needs to visit its nodes using the shortest route, without considering the limit of $d$, and the total length can be easily computed. We can find that if we adopt the strategy that we visit these nodes according to their DFS order(we merge the array of $a$ and $b$, and sort them according to the DFS order, if the first one is from $a$, we try to move the first piece to this position, otherwise use the second piece), and move the other piece one step closer to the present piece only if the next step of the present piece will violate the distance limit, then we can ensure the movement exactly just let each piece visit its necessary node without extra operations.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int N = 1e6 + 5;↵
int t[N * 2], nxt[N * 2], cnt, h[N];↵
int n, d;↵
void add(int x, int y) {↵
t[++cnt] = y;↵
nxt[cnt] = h[x];↵
h[x] = cnt;↵
}↵
int a[N], b[N];↵
bool f[2][N];↵
void dfs1(int x, int fa, int dis) {↵
a[dis] = x;↵
if (dis > d)↵
b[x] = a[dis - d];↵
else↵
b[x] = 1;↵
for (int i = h[x]; i; i = nxt[i]) {↵
if (t[i] == fa) continue;↵
dfs1(t[i], x, dis + 1);↵
}↵
}↵
void dfs2(int x, int fa, int tp) {↵
bool u = 0;↵
for (int i = h[x]; i; i = nxt[i]) {↵
if (t[i] == fa) continue;↵
dfs2(t[i], x, tp);↵
u |= f[tp][t[i]];↵
}↵
f[tp][x] |= u;↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
cin >> n >> d;↵
for (int i = 1; i < n; i++) {↵
int x, y;↵
cin >> x >> y;↵
add(x, y), add(y, x);↵
}↵
dfs1(1, 0, 1);↵
for (int i = 0; i <= 1; i++) {↵
int num;↵
cin >> num;↵
for (int j = 1; j <= num; j++) {↵
int x;↵
cin >> x;↵
f[i][x] = 1, f[i ^ 1][b[x]] = 1;↵
}↵
}↵
for (int i = 0; i <= 1; i++) dfs2(1, 0, i);↵
int ans = 0;↵
for (int i = 0; i <= 1; i++)↵
for (int j = 2; j <= n; j++)↵
if (f[i][j]) ans += 2;↵
cout << ans;↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1774F1] ↵
Idea: [user:little09,2022-12-17]↵
↵
<spoiler summary="Solution">↵
Let $X=\max x$.↵
↵
Think about what ‘Repeat’ is doing. Assuming the total damage is $tot$ ($tot$ is easy to calculate because it will be multiplied by $2$ after each ‘Repeat’ and be added after each ‘Attack’). After repeating, each pig with a current HP of $w$ ($w > tot$) will clone a pig with a HP of $w-tot$.↵
↵
Why? ‘Repeat’ will do what you just did again, so each original pig will certainly create a pig the same as it, and it will be attacked by $tot$, so it can be considered that a pig with $w-tot$ HP has been cloned.↵
↵
Next, the problem is to maintain a multiset $S$, which supports: adding a number, subtracting $x$ for all numbers, and inserting each number after subtracting $tot$. Find the number of positive elements in the final multiset.↵
↵
$tot$ in ‘Repeat’ after the first ‘Attack’ will multiply by $2$ every time, so it will exceed $X$ in $O(\log X)$ times. That is, only $O(\log X)$ ‘Repeat’ operations are effective. So we can maintain $S$ in brute force. Every time we do ‘Repeat’, we take out all the numbers larger than $tot$, then subtract and insert them again. Note that we may do some ‘Repeat’ operations when $tot=0$, which will result in the number of pigs generated before multiplying by $2$. Therefore, we also need to maintain the total multiplication.↵
↵
If you use map to maintain it, the time complexity is $O((n+X)\log ^2X)$. It can pass F1. You can also use some ways to make the time complexity $O((n+X)\log X)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
// Author: Little09↵
// Problem: F. Magician and Pigs (Easy Version)↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define ll long long↵
const ll mod = 998244353, inv = (mod + 1) / 2;↵
int n;↵
map<ll, ll> s;↵
ll tot, mul = 1, ts = 1;↵
inline void add(ll &x, ll y) { (x += y) >= mod && (x -= mod); }↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
cin >> n;↵
while (n--) {↵
int op;↵
cin >> op;↵
if (op == 1) {↵
ll x;↵
cin >> x;↵
add(s[x + tot], ts);↵
} else if (op == 2) {↵
ll x;↵
cin >> x;↵
tot += x;↵
} else if (tot <= 2e5) {↵
if (tot == 0)↵
mul = mul * 2 % mod, ts = ts * inv % mod;↵
else {↵
for (ll i = tot + 2e5; i > tot; i--) add(s[i + tot], s[i]);↵
tot *= 2;↵
}↵
}↵
}↵
ll res = 0;↵
for (auto i : s)↵
if (i.first > tot) add(res, i.second);↵
res = res * mul % mod;↵
cout << res;↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1774F2] ↵
Idea: [user:little09,2022-12-17]↵
↵
<spoiler summary="Solution">↵
For F1, there is another way. Consider every pig. When ``Repeat``, it will clone, and when ``Attack``, all its clones will be attacked together. Therefore, considering all the operations behind each pig, you can choose to reduce $x$ (the current total damage) or not when ``Repeat``, and you must choose to reduce $x$ when ``Attack``. Any final choice will become a pig (living or not).↵
↵
We just need to calculate how many ``Repeat`` choices can make a living pig. For ``Repeat`` of $x=0$, there is no difference between the two choices. For the ``Repeat`` of $x\geq 2\times 10^5$, it is obvious that you can only choose not to reduce $x$. Except for the above parts, there are only $O(\log x)$ choices. You can just find a subset or use knapsack to solve it. It can also pass F1 and the time complexity is $O((n+X)\log X)$.↵
↵
The bottleneck of using this method to do F2 lies in the backpack. The problem is that we need to find how many subsets whose sum $<x$ of of a set whose size is $O(\log X)$.↵
↵
Observation: if you sort the set, each element is greater than the sum of all elements smaller than it. We can use observation to solve the problem. Consider each element from large to small. Suppose you now need to find elements and subsets of $<x$. If the current element $\ge x$, it must not be selected; If the current element $<x$, if it is not selected, the following elements can be selected at will (the sum of all the following elements is less than it). It can be recursive. Thus, for a given $x$, we can find the number of subsets whose sum $<x$ within $O(\log X)$.↵
↵
The time complexity is $O(n\log X)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
// Author: Little09↵
// Problem: F. Magician and Pigs↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define ll long long↵
#define mem(x) memset(x, 0, sizeof(x))↵
#define endl "\n"↵
#define printYes cout << "Yes\n"↵
#define printYES cout << "YES\n"↵
#define printNo cout << "No\n"↵
#define printNO cout << "NO\n"↵
#define lowbit(x) ((x) & (-(x)))↵
#define pb push_back↵
#define mp make_pair↵
#define pii pair<int, int>↵
#define fi first↵
#define se second↵
↵
const ll inf = 1000000000000000000;↵
// const ll inf=1000000000;↵
const ll mod = 998244353;↵
// const ll mod=1000000007;↵
↵
const int N = 800005;↵
int n, m;↵
ll a[N], b[N], c[N], cnt, s[N], d[N], cntd;↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
cin >> n;↵
ll maxs = 1e9, sum = 0;↵
for (int i = 1; i <= n; i++) {↵
cin >> a[i];↵
if (a[i] != 3) cin >> b[i];↵
if (a[i] == 2) sum += b[i];↵
sum = min(sum, maxs);↵
if (a[i] == 3) b[i] = sum, sum = sum * 2;↵
sum = min(sum, maxs);↵
}↵
sum = 0;↵
ll res = 1, ans = 0;↵
for (int i = n; i >= 1; i--) {↵
if (a[i] == 2)↵
sum += b[i];↵
else if (a[i] == 3) {↵
if (b[i] == maxs) continue;↵
if (b[i] == 0) {↵
res = res * 2 % mod;↵
continue;↵
}↵
c[++cnt] = b[i];↵
} else {↵
b[i] -= sum;↵
if (b[i] <= 0) continue;↵
ll su = 0, r = b[i];↵
for (int j = 1; j <= cnt; j++) {↵
if (r > c[j]) {↵
su = (su + (1ll << (cnt - j))) % mod;↵
r -= c[j];↵
}↵
}↵
su = (su + 1) % mod;↵
ans = (ans + su * res) % mod;↵
}↵
}↵
cout << ans;↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1774G] ↵
Idea: [user:ChthollyNotaSeniorious,2022-12-17] and [user:DataStructures,2022-12-17]↵
↵
<spoiler summary="Hint 1">↵
If there exist two segments $(l_1, r_1), (l_2, r_2)$ such that $l_1 \le l_2 \le r_2 \le r_1$ and we choose $(l_1, r_1)$, number of ways of choosing $(l_2, r_2)$ at the same time will be equal to that of not choosing. Hence if we choose $(l_1, r_1)$, the signed number of ways will be $0$. So we can delete $(l_1, r_1)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
It can be proved that the absolute value of every $f_{l,r} - g_{l,r}$ doesn't exceed $1$.↵
↵
Proof: First, find segments $(l_i, r_i)$ which are completely contained by $(l, r)$.↵
↵
Let us sort $(l_i, r_i)$ in ascending order of $l_i$. As there does not exist a segment that contains another, $r_i$ are also sorted.↵
↵
Assume that $l_2 < l_3 \leq r_1$ and $r_3 \geq r_2$. If we choose segments $1$ and $3$, choosing $2$ or not will be the same except for the sign. So $3$ is useless. So we can delete such useless segments. After the process, $l_3 > r_1, l_4 > r_2, \cdots$ will be held. If $[l_1, r_1] \cup [l_2, r_2] \cup \cdots \cup [l_k, r_k] = [l, r]$, answer will be $(-1)^k$, else answer will be $0$.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
This picture shows what the segments eventually are like:↵
↵
↵
↵
For $[l_i, r_i]$, we can find the lowest $j$ such that $l_j > r_j$ and construct a tree by linking such $i$ and $j$. Then the LCA of $1$ and $2$ will be $5$, where the answer becomes 0.↵
↵
So we can get the answer quickly by simply finding the LCA of two segments.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#define File(a) freopen(a ".in", "r", stdin), freopen(a ".out", "w", stdout)↵
↵
using tp = std::tuple<int, int, int>;↵
const int sgn[] = {1, 998244352};↵
const int N = 200005;↵
↵
int x[N], y[N];↵
std::vector<tp> V;↵
bool del[N];↵
int fa[20][N];↵
int m, q;↵
↵
int main() {↵
scanf("%d %d", &m, &q);↵
for (int i = 1; i <= m; ++i)↵
scanf("%d %d", x + i, y + i), V.emplace_back(y[i], -x[i], i);↵
std::sort(V.begin(), V.end());↵
int mxl = 0;↵
for (auto [y, x, i] : V) {↵
if (-x <= mxl) del[i] = true;↵
mxl = std::max(mxl, -x);↵
}↵
V.clear();↵
x[m + 1] = y[m + 1] = 1e9 + 1;↵
for (int i = 1; i <= m + 1; ++i) {↵
if (!del[i]) V.emplace_back(x[i], y[i], i);↵
}↵
std::sort(V.begin(), V.end());↵
for (auto [x, y, id] : V) {↵
int t = std::get<2>(*std::lower_bound(V.begin(), V.end(), tp{y + 1, 0, 0}));↵
fa[0][id] = t;↵
}↵
fa[0][m + 1] = m + 1;↵
for (int k = 1; k <= 17; ++k) {↵
for (int i = 1; i <= m + 1; ++i) fa[k][i] = fa[k - 1][fa[k - 1][i]];↵
}↵
for (int i = 1; i <= q; ++i) {↵
int l, r;↵
scanf("%d %d", &l, &r);↵
int u = std::lower_bound(V.begin(), V.end(), tp{l, 0, 0}) - V.begin(), v = u + 1;↵
u = std::get<2>(V[u]);↵
if (x[u] != l || y[u] > r) {↵
puts("0");↵
continue;↵
}↵
if (y[u] == r) {↵
puts("998244352");↵
continue;↵
}↵
v = std::get<2>(V[v]);↵
if (y[v] > r || x[v] > y[u]) {↵
puts("0");↵
continue;↵
}↵
int numu = 0, numv = 0;↵
for (int i = 17; i >= 0; --i) {↵
if (y[fa[i][u]] <= r) {↵
u = fa[i][u];↵
numu += !i;↵
}↵
}↵
for (int i = 17; i >= 0; --i) {↵
if (y[fa[i][v]] <= r) {↵
v = fa[i][v];↵
numv += !i;↵
}↵
}↵
if (u == v || (y[u] != r && y[v] != r))↵
puts("0");↵
else↵
printf("%d\n", sgn[numu ^ numv]);↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1774H] ↵
Idea: [user:Ecrade_,2022-12-17]↵
↵
To be added...
