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  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  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  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  562 563 Similarly, one can come up with an approach when $n$ is even: 564 565  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  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 ```