codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1774.md (27155B)


      1 Source: https://codeforces.com/blog/entry/110184
      2 
      3 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 good 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.
      4 
      5 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.
      6 
      7 [1774A - Add Plus Minus Sign](/contest/1774/problem/A)  
      8 Idea: [Cirno_9baka](/profile/Cirno_9baka "International Grandmaster Cirno_9baka")
      9 
     10 **Solution**
     11 
     12 The answer is the number of $1$s modulo $2$.
     13 
     14 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$.
     15 
     16 **Code**
     17 
     18 ```
     19 #include <bits/stdc++.h>
     20 using namespace std;
     21 
     22 char c[1005];
     23 int main() {
     24   int t;
     25   scanf("%d", &t);
     26   int n;
     27   while (t--) {
     28     scanf("%d", &n);
     29     scanf("%s", c + 1);
     30     int u = 0;
     31     for (int i = 1; i <= n; ++i) {
     32       bool fl = (c[i] == '1') && u;
     33       u ^= (c[i] - '0');
     34       if (i != 1) putchar(fl ? '-' : '+');
     35     }
     36     putchar('\n');
     37   }
     38 }
     39 ```
     40 
     41 [1774B - Coloring](/contest/1774/problem/B)  
     42 Idea: [Cirno_9baka](/profile/Cirno_9baka "International Grandmaster Cirno_9baka")
     43 
     44 **Solution**
     45 
     46 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$.
     47 
     48 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.
     49 
     50 All $a$ that satisfies the conditions above is valid. We can construct a coloring using the method below:
     51 
     52 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.
     53 
     54 Then we pick out all colors $i$ that $a_i \lt \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+1$. when one color is used up, we begin to use the next color)
     55 
     56 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.
     57 
     58 This method will always give a valid construction.
     59 
     60 **Code**
     61 
     62 ```
     63 #include <bits/stdc++.h>
     64 using namespace std;
     65 
     66 int main() {
     67   int t;
     68   scanf("%d", &t);
     69   while (t--) {
     70     int n, m, k;
     71     scanf("%d %d %d", &n, &m, &k);
     72     int fl = 0;
     73     for (int i = 1; i <= m; ++i) {
     74       int a;
     75       scanf("%d", &a);
     76       if (a == (n + k - 1) / k) ++fl;
     77       if (a > (n + k - 1) / k) fl = 1 << 30;
     78     }
     79     puts(fl <= (n - 1) % k + 1 ? "YES" : "NO");
     80   }
     81 }
     82 ```
     83 
     84 [1774C - Ice and Fire](/contest/1774/problem/C)  
     85 Idea: [Little09](/profile/Little09 "Grandmaster Little09")
     86 
     87 **Solution**
     88 
     89 We define $f_i$ to mean that the maximum $x$ satisfies $s_{i-x+1}=s_{i-x+2}=...=s_{i}$.
     90 
     91 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$.
     92 
     93 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:
     94 
     95 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 \lt x$, the $i$-th player cannot win.
     96 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.
     97 
     98 For $s_{n-1}=0$, the situation is similar and it will not be repeated here.
     99 
    100 **Code**
    101 
    102 ```
    103 #include <bits/stdc++.h>
    104 using namespace std;
    105 
    106 const int N = 300005;
    107 int T, n, ps[2];
    108 char a[N];
    109 
    110 void solve() {
    111   scanf("%d %s", &n, a + 1);
    112   ps[0] = ps[1] = 0;
    113   for (int i = 1; i < n; ++i) {
    114     ps[a[i] - 48] = i;
    115     if (a[i] == '0')
    116       printf("%d ", ps[1] + 1);
    117     else
    118       printf("%d ", ps[0] + 1);
    119   }
    120   putchar('\n');
    121 }
    122 int main() {
    123   scanf("%d", &T);
    124   while (T--) solve();
    125   return 0;
    126 }
    127 ```
    128 
    129 [1774D - Same Count One](/contest/1774/problem/D)  
    130 Idea: [mejiamejia](/profile/mejiamejia "Expert mejiamejia") and [AquaMoon](/profile/AquaMoon "International Master AquaMoon")
    131 
    132 **Solution**
    133 
    134 Considering that we need to make the number of $1\text{s}$ in each array the same, we should calculate the sum of $1\text{s}$, and every array has $sum / n$ $1\text{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\text{s}$ in this array is not enough, then we need to turn some $0\text{s}$ into $1\text{s}$; If the number of $1\text{s}$ in this array is more than we need, then some $1\text{s}$ should be turned into $0\text{s}$. It can be proved that as long as the total number of $1\text{s}$ is a multiple of $n$, the number of $1\text{s}$ in each array can be made the same through exchanges.
    135 
    136 **Code**
    137 
    138 ```
    139 #include <bits/stdc++.h>
    140 
    141 int main() {
    142   int T;
    143   scanf("%d", &T);
    144   while (T--) {
    145     int n, m;
    146     scanf("%d %d", &n, &m);
    147     std::vector<std::vector<int>> A(n, std::vector<int>(m, 0));
    148     std::vector<int> sum(n, 0);
    149     for (int i = 0; i < n; ++i) {
    150       for (int j = 0; j < m; ++j) {
    151         scanf("%d", &A[i][j]);
    152         sum[i] += A[i][j];
    153       }
    154     }
    155     int tot = 0;
    156     for (int i = 0; i < n; ++i) tot += sum[i];
    157     if (tot % n) {
    158       puts("-1");
    159       continue;
    160     }
    161     tot /= n;
    162     std::vector<std::tuple<int, int, int>> ans;
    163     std::vector<int> Vg, Vl;
    164     Vg.reserve(n), Vl.reserve(n);
    165     for (int j = 0; j < m; ++j) {
    166       for (int i = 0; i < n; ++i) {
    167         if (sum[i] > tot && A[i][j]) Vg.push_back(i);
    168         if (sum[i] < tot && !A[i][j]) Vl.push_back(i);
    169       }
    170       for (int i = 0; i < (int)std::min(Vl.size(), Vg.size()); ++i) {
    171         ++sum[Vl[i]], --sum[Vg[i]];
    172         ans.emplace_back(Vl[i], Vg[i], j);
    173       }
    174       Vl.clear(), Vg.clear();
    175     }
    176     printf("%d\n", (int)ans.size());
    177     for (auto [i, j, k] : ans) printf("%d %d %d\n", i + 1, j + 1, k + 1);
    178   }
    179   return 0;
    180 }
    181 ```
    182 
    183 [1774E - Two Chess Pieces](/contest/1774/problem/E)  
    184 Idea: [Cirno_9baka](/profile/Cirno_9baka "International Grandmaster Cirno_9baka")
    185 
    186 **Solution**
    187 
    188 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$.
    189 
    190 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.
    191 
    192 **Code**
    193 
    194 ```
    195 #include <bits/stdc++.h>
    196 using namespace std;
    197 
    198 const int N = 1e6 + 5;
    199 int t[N * 2], nxt[N * 2], cnt, h[N];
    200 int n, d;
    201 void add(int x, int y) {
    202   t[++cnt] = y;
    203   nxt[cnt] = h[x];
    204   h[x] = cnt;
    205 }
    206 int a[N], b[N];
    207 bool f[2][N];
    208 void dfs1(int x, int fa, int dis) {
    209   a[dis] = x;
    210   if (dis > d)
    211     b[x] = a[dis - d];
    212   else
    213     b[x] = 1;
    214   for (int i = h[x]; i; i = nxt[i]) {
    215     if (t[i] == fa) continue;
    216     dfs1(t[i], x, dis + 1);
    217   }
    218 }
    219 void dfs2(int x, int fa, int tp) {
    220   bool u = 0;
    221   for (int i = h[x]; i; i = nxt[i]) {
    222     if (t[i] == fa) continue;
    223     dfs2(t[i], x, tp);
    224     u |= f[tp][t[i]];
    225   }
    226   f[tp][x] |= u;
    227 }
    228 
    229 int main() {
    230   ios_base::sync_with_stdio(false);
    231   cin.tie(0);
    232   cout.tie(0);
    233   cin >> n >> d;
    234   for (int i = 1; i < n; i++) {
    235     int x, y;
    236     cin >> x >> y;
    237     add(x, y), add(y, x);
    238   }
    239   dfs1(1, 0, 1);
    240   for (int i = 0; i <= 1; i++) {
    241     int num;
    242     cin >> num;
    243     for (int j = 1; j <= num; j++) {
    244       int x;
    245       cin >> x;
    246       f[i][x] = 1, f[i ^ 1][b[x]] = 1;
    247     }
    248   }
    249   for (int i = 0; i <= 1; i++) dfs2(1, 0, i);
    250   int ans = 0;
    251   for (int i = 0; i <= 1; i++)
    252     for (int j = 2; j <= n; j++)
    253       if (f[i][j]) ans += 2;
    254   cout << ans;
    255   return 0;
    256 }
    257 ```
    258 
    259 [1774F1 - Magician and Pigs (Easy Version)](/contest/1774/problem/F1)  
    260 Idea: [Little09](/profile/Little09 "Grandmaster Little09")
    261 
    262 **Solution**
    263 
    264 Let $X=\max x$.
    265 
    266 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 \gt tot$) will clone a pig with a HP of $w-tot$.
    267 
    268 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.
    269 
    270 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.
    271 
    272 $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.
    273 
    274 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)$.
    275 
    276 **Code**
    277 
    278 ```
    279 // Author: Little09
    280 // Problem: F. Magician and Pigs (Easy Version)
    281 
    282 #include <bits/stdc++.h>
    283 using namespace std;
    284 
    285 #define ll long long
    286 const ll mod = 998244353, inv = (mod + 1) / 2;
    287 int n;
    288 map<ll, ll> s;
    289 ll tot, mul = 1, ts = 1;
    290 inline void add(ll &x, ll y) { (x += y) >= mod && (x -= mod); }
    291 
    292 int main() {
    293   ios_base::sync_with_stdio(false);
    294   cin.tie(0);
    295   cout.tie(0);
    296   cin >> n;
    297   while (n--) {
    298     int op;
    299     cin >> op;
    300     if (op == 1) {
    301       ll x;
    302       cin >> x;
    303       add(s[x + tot], ts);
    304     } else if (op == 2) {
    305       ll x;
    306       cin >> x;
    307       tot += x;
    308     } else if (tot <= 2e5) {
    309       if (tot == 0)
    310         mul = mul * 2 % mod, ts = ts * inv % mod;
    311       else {
    312         for (ll i = tot + 2e5; i > tot; i--) add(s[i + tot], s[i]);
    313         tot *= 2;
    314       }
    315     }
    316   }
    317   ll res = 0;
    318   for (auto i : s)
    319     if (i.first > tot) add(res, i.second);
    320   res = res * mul % mod;
    321   cout << res;
    322   return 0;
    323 }
    324 ```
    325 
    326 [1774F2 - Magician and Pigs (Hard Version)](/contest/1774/problem/F2)  
    327 Idea: [Little09](/profile/Little09 "Grandmaster Little09")
    328 
    329 **Solution**
    330 
    331 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).
    332 
    333 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)$.
    334 
    335 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 $ \lt x$ of of a set whose size is $O(\log X)$.
    336 
    337 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 $ \lt x$. If the current element $\ge x$, it must not be selected; If the current element $ \lt 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 $ \lt x$ within $O(\log X)$.
    338 
    339 The time complexity is $O(n\log X)$.
    340 
    341 **Code**
    342 
    343 ```
    344 // Author: Little09
    345 // Problem: F. Magician and Pigs
    346 
    347 #include <bits/stdc++.h>
    348 using namespace std;
    349 
    350 #define ll long long
    351 #define mem(x) memset(x, 0, sizeof(x))
    352 #define endl "\n"
    353 #define printYes cout << "Yes\n"
    354 #define printYES cout << "YES\n"
    355 #define printNo cout << "No\n"
    356 #define printNO cout << "NO\n"
    357 #define lowbit(x) ((x) & (-(x)))
    358 #define pb push_back
    359 #define mp make_pair
    360 #define pii pair<int, int>
    361 #define fi first
    362 #define se second
    363 
    364 const ll inf = 1000000000000000000;
    365 // const ll inf=1000000000;
    366 const ll mod = 998244353;
    367 // const ll mod=1000000007;
    368 
    369 const int N = 800005;
    370 int n, m;
    371 ll a[N], b[N], c[N], cnt, s[N], d[N], cntd;
    372 
    373 int main() {
    374   ios_base::sync_with_stdio(false);
    375   cin.tie(0);
    376   cout.tie(0);
    377   cin >> n;
    378   ll maxs = 1e9, sum = 0;
    379   for (int i = 1; i <= n; i++) {
    380     cin >> a[i];
    381     if (a[i] != 3) cin >> b[i];
    382     if (a[i] == 2) sum += b[i];
    383     sum = min(sum, maxs);
    384     if (a[i] == 3) b[i] = sum, sum = sum * 2;
    385     sum = min(sum, maxs);
    386   }
    387   sum = 0;
    388   ll res = 1, ans = 0;
    389   for (int i = n; i >= 1; i--) {
    390     if (a[i] == 2)
    391       sum += b[i];
    392     else if (a[i] == 3) {
    393       if (b[i] == maxs) continue;
    394       if (b[i] == 0) {
    395         res = res * 2 % mod;
    396         continue;
    397       }
    398       c[++cnt] = b[i];
    399     } else {
    400       b[i] -= sum;
    401       if (b[i] <= 0) continue;
    402       ll su = 0, r = b[i];
    403       for (int j = 1; j <= cnt; j++) {
    404         if (r > c[j]) {
    405           su = (su + (1ll << (cnt - j))) % mod;
    406           r -= c[j];
    407         }
    408       }
    409       su = (su + 1) % mod;
    410       ans = (ans + su * res) % mod;
    411     }
    412   }
    413   cout << ans;
    414   return 0;
    415 }
    416 ```
    417 
    418 [1774G - Segment Covering](/contest/1774/problem/G)  
    419 Idea: [ChthollyNotaSeniorious](/profile/ChthollyNotaSeniorious "Master ChthollyNotaSeniorious") and [JianfengZhu](/profile/JianfengZhu "Grandmaster JianfengZhu")
    420 
    421 **Hint 1**
    422 
    423 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)$.
    424 
    425 **Hint 2**
    426 
    427 It can be proved that the absolute value of every $f_{l,r} - g_{l,r}$ doesn't exceed $1$.
    428 
    429 Proof: First, find segments $(l_i, r_i)$ which are completely contained by $(l, r)$.
    430 
    431 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.
    432 
    433 Assume that $l_2 \lt 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 \gt r_1, l_4 \gt 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$.
    434 
    435 **Solution**
    436 
    437 This picture shows what the segments eventually are like:
    438 
    439 ![ ](https://espresso.codeforces.com/f531cf0b4320ec06f9b2c30cd3bf75ddf931f2d6.png)
    440 
    441 For $[l_i, r_i]$, we can find the lowest $j$ such that $l_j \gt r_i$ 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.
    442 
    443 So we can get the answer of $(ql, qr)$ quickly by simply finding the LCA of two segments -- the segment starting with $ql$ (if no segment starts with $ql$, the answer is $0$), and the first segment whose $l$ is greater than $ql$ (if it do not intersect with the previous segment, the answer is $0$).
    444 
    445 And find the segment ending with $qr$. If it is on the path of the two segments, the answer will be $\pm 1$. Else, the answer will be $0$.
    446 
    447 **Code**
    448 
    449 ```
    450 #include <bits/stdc++.h>
    451 
    452 #define File(a) freopen(a ".in", "r", stdin), freopen(a ".out", "w", stdout)
    453 
    454 using tp = std::tuple<int, int, int>;
    455 const int sgn[] = {1, 998244352};
    456 const int N = 200005;
    457 
    458 int x[N], y[N];
    459 std::vector<tp> V;
    460 bool del[N];
    461 int fa[20][N];
    462 int m, q;
    463 
    464 int main() {
    465   scanf("%d %d", &m, &q);
    466   for (int i = 1; i <= m; ++i)
    467     scanf("%d %d", x + i, y + i), V.emplace_back(y[i], -x[i], i);
    468   std::sort(V.begin(), V.end());
    469   int mxl = 0;
    470   for (auto [y, x, i] : V) {
    471     if (-x <= mxl) del[i] = true;
    472     mxl = std::max(mxl, -x);
    473   }
    474   V.clear();
    475   x[m + 1] = y[m + 1] = 1e9 + 1;
    476   for (int i = 1; i <= m + 1; ++i) {
    477     if (!del[i]) V.emplace_back(x[i], y[i], i);
    478   }
    479   std::sort(V.begin(), V.end());
    480   for (auto [x, y, id] : V) {
    481     int t = std::get<2>(*std::lower_bound(V.begin(), V.end(), tp{y + 1, 0, 0}));
    482     fa[0][id] = t;
    483   }
    484   fa[0][m + 1] = m + 1;
    485   for (int k = 1; k <= 17; ++k) {
    486     for (int i = 1; i <= m + 1; ++i) fa[k][i] = fa[k - 1][fa[k - 1][i]];
    487   }
    488   for (int i = 1; i <= q; ++i) {
    489     int l, r;
    490     scanf("%d %d", &l, &r);
    491     int u = std::lower_bound(V.begin(), V.end(), tp{l, 0, 0}) - V.begin(), v = u + 1;
    492     u = std::get<2>(V[u]);
    493     if (x[u] != l || y[u] > r) {
    494       puts("0");
    495       continue;
    496     }
    497     if (y[u] == r) {
    498       puts("998244352");
    499       continue;
    500     }
    501     v = std::get<2>(V[v]);
    502     if (y[v] > r || x[v] > y[u]) {
    503       puts("0");
    504       continue;
    505     }
    506     int numu = 0, numv = 0;
    507     for (int i = 17; i >= 0; --i) {
    508       if (y[fa[i][u]] <= r) {
    509         u = fa[i][u];
    510         numu += !i;
    511       }
    512     }
    513     for (int i = 17; i >= 0; --i) {
    514       if (y[fa[i][v]] <= r) {
    515         v = fa[i][v];
    516         numv += !i;
    517       }
    518     }
    519     if (u == v || (y[u] != r && y[v] != r))
    520       puts("0");
    521     else
    522       printf("%d\n", sgn[numu ^ numv]);
    523   }
    524   return 0;
    525 }
    526 ```
    527 
    528 [1774H - Maximum Permutation](/contest/1774/problem/H)  
    529 Idea: [Ecrade_](/profile/Ecrade_ "Grandmaster Ecrade_")
    530 
    531 **Solution**
    532 
    533 When it seems to be hard to come up with the whole solution directly, simplified questions can often be a great helper. So first let us consider the case where $n$ is the multiple of $k$.
    534 
    535 Let $t=\frac{n}{k}$.
    536 
    537 What is the largest value one can obtain theoretically? Pick out $t$ subsegments $a_{[1:k]},a_{[k+1:2k]},\dots,a_{[n-k+1:n]}$, and one can see that the answer cannot be greater than the average value of the sum of each subsegment, that is $\frac{n(n+1)}{2t}=\frac{k(n+1)}{2}$.
    538 
    539 #### Case 1: $k$ is even
    540 
    541 If $k$ is even, one can construct $a=[1,n,2,n-1,3,n-2,\dots,\frac{n}{2},\frac{n}{2}+1]$ to reach the maximum value.
    542 
    543 #### Case 2: $k$ is odd
    544 
    545 For easy understanding let us put $a_{[1:k]},a_{[k+1:2k]},\dots,a_{[n-k+1:n]}$ into a $t\times k$ table from top to bottom like this:
    546 
    547 ![1.png](https://espresso.codeforces.com/dbbaf8dc17eb165ba8ad3f15326c22ff455bdf56.png)
    548 
    549 Note that the difference value between two consecutive subsegments is equal to the difference value between two values in the same column in this table. It inspires us to fill in the last $k-3$ columns in an S-shaped way like this:
    550 
    551 ![2.png](https://espresso.codeforces.com/94117a59c33b0814c5c0b26e55427de041de58ea.png)
    552 
    553 Then our goal is to split the remaining $3t$ numbers into $3$ groups and minimize the difference value between the sum of each group.
    554 
    555 If $n$ is odd, the theoretical maximum value mentioned above is an integer, and the sum of each group must be equal to reach that value. Otherwise, the theoretical maximum value mentioned above is not an integer, and the sum of each group cannot be determined. So let us first consider the case where $n$ is odd. A feasible approach to split the numbers is as follows:
    556 
    557 $(1,\frac{3t+1}{2},3t),(3,\frac{3t-1}{2},3t-1),\dots,(t,t+1,\frac{5t+1}{2}),(2,2t,\frac{5t-1}{2}),(4,2t-1,\frac{5t-3}{2}),\dots,(t-1,\frac{3t+3}{2},2t+1)$
    558 
    559 Then fill them into the table:
    560 
    561 ![3.png](https://espresso.codeforces.com/6f41da9df298f19a25338d152d74008e69b50168.png)
    562 
    563 Similarly, one can come up with an approach when $n$ is even:
    564 
    565 ![4.png](https://espresso.codeforces.com/50b912bc634b5d57c677d2d7b8469825ece64185.png)
    566 
    567 Okay, it's time for us to go back to the original problem.
    568 
    569 Let $n=qk+r\ (r,q\in \mathbb{N},1\le r \lt k)$.
    570 
    571 Split $n$ elements like this:
    572 
    573 ![5.png](https://espresso.codeforces.com/609751b58367cf157c698822d9c4119ced07432b.png)
    574 
    575 As shown in the picture, there are $(q+1)$ red subsegments with $r$ elements each, and $q$ blue subsegments with $(k-r)$ elements each. What is the largest value one can obtain theoretically now? Pick out $q$ non-intersecting subsegments consisting of a whole red subsegment and a whole blue segement each, and one can see that the answer cannot be greater than the average value of the sum of each subsegment, that is the sum of $1 \thicksim n$ subtracted by the sum of any whole red subsegment, then divide by $q$. Similarly, the answer cannot be greater than the sum of $1 \thicksim n$ added by the sum of any whole blue subsegment, then divide by $(q+1)$.
    576 
    577 Thus, our goal is to make the maximum sum of each red subsegment the minimum, and make the minimum sum of each blue subsegment the maximum. Now here comes an interesting claim: it can be proved that,
    578 
    579 * If $r\neq 1$ and $k-r\neq 1$, one can fill the red subsegments using the method when $n$ is the multiple of $k$ (here $n'=(q+1)r,k'=r$ ) with $1\thicksim (q+1)r$, and the blue subsegments (here $n'=q(k-r),k'=k-r$ ) with the remaining numbers;
    580 * If $r=1$, one can fill the red subsegments with $1\thicksim (q+1)$ from left to right, and the first element of the blue subsegments with $(q+2)\thicksim (2q+1)$ from right to left, and the blue subsegments without the first element using the method when $n$ is the multiple of $k$ (here $n'=q(k-2),k'=k-2$ ) with the remaining numbers;
    581 * If $k-r=1$ and $q=1$, one can let $a_k=n$, and fill the rest two subsegments using the method when $n$ is the multiple of $k$ (here $n'=n-1,k'=k-1$ ) with the remaining numbers;
    582 * If $k-r=1$ and $q \gt 1$, one can fill the blue subsegments with $(n-q+1)\thicksim n$ from right to left, and the first element of the red subsegments with $1\thicksim (q+1)$ from right to left, and the red subsegments without the first element using the method when $n$ is the multiple of $k$ (here $n'=(q+1)(r-1),k'=r-1$ ) with the remaining numbers,
    583 
    584 then the constraints can both be satisfied and the value of the permutation is theoretically maximum. The proof is omitted here.
    585 
    586 Time complexity: $O(\sum n)$
    587 
    588 **Bonus: solve the problem if $k\ge 2$.**
    589 
    590 **Code**
    591 
    592 ```
    593 #include<bits/stdc++.h>
    594 using namespace std;
    595 
    596 typedef long long ll;
    597 ll t,n,k,seq[100009],ans[100009];
    598 inline ll read(){
    599   ll s = 0,w = 1;
    600   char ch = getchar();
    601   while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
    602   while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
    603   return s * w;
    604 }
    605 
    606 ll f(ll x,ll y,ll k){return (x - 1) * k + y;}
    607 void get(ll n,ll k){
    608   if (!(k & 1)){
    609     for (ll i = 1;i <= n >> 1;i += 1) seq[(i << 1) - 1] = i,seq[i << 1] = n + 1 - i;
    610     return;
    611   }
    612   ll m = n / k,cur = 3 * m;
    613   for (ll i = 4;i <= k;i += 1){
    614     if (i & 1) for (ll j = m;j >= 1;j -= 1) seq[f(j,i,k)] = ++ cur;
    615     else for (ll j = 1;j <= m;j += 1) seq[f(j,i,k)] = ++ cur;
    616   }
    617   for (ll i = 1;i <= (m + 1 >> 1);i += 1){
    618     seq[f(i,1,k)] = (i << 1) - 1;
    619     seq[f(i,2,k)] = ((3 * m + 3) >> 1) - i;
    620     seq[f(i,3,k)] = 3 * m - i + 1;
    621   }
    622   for (ll i = (m + 3 >> 1);i <= m;i += 1){
    623     ll delta = i - (m + 3 >> 1);
    624     seq[f(i,1,k)] = ((3 * m + 3) >> 1) + delta;
    625     seq[f(i,2,k)] = (m << 1) + 1 + delta;
    626     seq[f(i,3,k)] = m - (m & 1) - (delta << 1);
    627   }
    628 }
    629 void print(){
    630   ll res = 0,sum = 0;
    631   for (ll i = 1;i <= k;i += 1) sum += ans[i];
    632   res = sum;
    633   for (ll i = k + 1;i <= n;i += 1) sum += ans[i] - ans[i - k],res = min(res,sum);
    634   printf("%lld\n",res);
    635   for (ll i = 1;i <= n;i += 1) printf("%lld ",ans[i]);
    636   puts("");
    637 }
    638 
    639 int main(){
    640   t = read();
    641   while (t --){
    642     n = read(),k = read();
    643     if (!(n % k)){
    644       get(n,k);
    645       for (ll i = 1;i <= n;i += 1) ans[i] = seq[i];
    646       print();
    647       continue;
    648     }
    649     ll q = n / k,r = n % k;
    650     if (r == 1){
    651       ll cur = 0,delta = (q << 1) + 1;
    652       for (ll i = 1;i <= n;i += k) ans[i] = ++ cur;
    653       for (ll i = n - k + 1;i >= 2;i -= k) ans[i] = ++ cur;
    654       get(q * (k - 2),k - 2),cur = 0;
    655       for (ll i = 3;i <= n;i += k) for (ll j = i;j <= i + k - 3;j += 1) ans[j] = seq[++ cur] + delta;
    656       print();
    657       continue;
    658     }
    659     if (k - r == 1){
    660       if (q == 1){
    661         ll cur = 0;
    662         ans[k] = n;
    663         get(n - 1,k - 1);
    664         for (ll i = 1;i < k;i += 1) ans[i] = seq[++ cur];
    665         for (ll i = k + 1;i <= n;i += 1) ans[i] = seq[++ cur];
    666         print();
    667         continue;
    668       }
    669       ll cur = n + 1,delta = q + 1;
    670       for (ll i = k;i <= n;i += k) ans[i] = -- cur;
    671       cur = 0;
    672       for (ll i = 1;i <= n;i += k) ans[i] = ++ cur;
    673       get((q + 1) * (r - 1),r - 1),cur = 0;
    674       for (ll i = 2;i <= n;i += k) for (ll j = i;j <= i + r - 2;j += 1) ans[j] = seq[++ cur] + delta;
    675       print();
    676       continue;
    677     }
    678     ll cur = 0,delta = (q + 1) * r;
    679     get((q + 1) * r,r);
    680     for (ll i = 1;i <= n;i += k) for (ll j = i;j <= i + r - 1;j += 1) ans[j] = seq[++ cur];
    681     get(q * (k - r),k - r),cur = 0;
    682     for (ll i = r + 1;i <= n;i += k) for (ll j = i;j <= i + (k - r) - 1;j += 1) ans[j] = seq[++ cur] + delta;
    683     print();
    684   }
    685   return 0;
    686 }
    687 ```