2162.md (25943B)
1 Source: https://codeforces.com/blog/entry/147242 2 3 [2162A - Красивое среднее](/contest/2162/problem/A "Codeforces Round 1059 (Div. 3)") 4 5 Idea: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever") Preparation: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever") 6 7 **Solution** 8 9 Let's say we have a sequence of numbers with an average equal to $k$. 10 11 Adding a number greater than $k$ increases the average, while adding a smaller one decreases it. 12 13 Therefore, the maximum average subarray is formed by taking the maximum element, since including anything smaller would only lower the average. 14 15 Hence, the final answer is the maximum element of the given array. 16 17 Time Complexity: $O(n)$ per testcase. 18 19 **Implementation** 20 21 ``` 22 #include<bits/stdc++.h> 23 using namespace std; 24 25 #define ll long long 26 27 int main(){ 28 29 int t; 30 cin >> t; 31 32 while(t--){ 33 int n; 34 cin >> n; 35 36 vector<int> a(n); 37 for(int i = 0; i < n; i++) cin >> a[i]; 38 39 cout << *max_element(a.begin(), a.end()) << endl; 40 } 41 42 return 0; 43 } 44 ``` 45 46 [2162B - Красивая строка](/contest/2162/problem/B "Codeforces Round 1059 (Div. 3)") 47 48 Idea: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever") Preparation: [tridipta2806](/profile/tridipta2806 "Эксперт tridipta2806") 49 50 **Solution** 51 52 We need to find a non-decreasing subsequence $p$ such that, after removing its characters from the string $s$, the remaining string $x$ becomes a palindrome. 53 54 Observe that if we choose $p$ to consist of all the $0$'s in $s$, then $x$ will contain only $1$'s, which always forms a palindrome. Similarly, if we take $p$ as all the $1$'s, then $x$ will contain only $0$'s, which is also a palindrome. 55 56 In both cases, $p$ is clearly a non-decreasing subsequence (since all its elements are equal). 57 58 Therefore, a valid solution always exists — we can simply output the indices of either all $0$'s or all $1$'s in the string. 59 60 Time Complexity: $O(n)$ per testcase. 61 62 **Implementation** 63 64 ``` 65 #include<bits/stdc++.h> 66 using namespace std; 67 68 #define ll long long 69 70 int main(){ 71 72 int t; 73 cin >> t; 74 75 while(t--){ 76 int n; 77 cin >> n; 78 79 string s; 80 cin >> s; 81 82 vector<int> pos; 83 for(int i = 0; i < n; i++) if(s[i] == '0') pos.push_back(i + 1); 84 85 cout << (int)pos.size() << '\n'; 86 for(auto& z : pos) cout << z << ' '; 87 88 cout << '\n'; 89 } 90 91 return 0; 92 } 93 ``` 94 95 [2162C - Красивый XOR](/contest/2162/problem/C "Codeforces Round 1059 (Div. 3)") 96 97 Idea: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever") Preparation: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever") 98 99 **Solution** 100 101 We are allowed to choose any $x$ such that $0 \le x \le a$ and set $a := a \oplus x$. Our goal is to make $a$ equal to $b$. 102 103 Let's think of the binary representation of $a$. Consider the highest set bit (most significant bit) of $a$ and let's assume its position is $\operatorname{msb}(a)$. 104 105 At each operation, we are choosing $x \le a$, which implies that $\operatorname{msb}(x) \le \operatorname{msb}(a)$ (otherwise, we have $x \gt a$). 106 107 $ \displaystyle \begin{matrix} a = (00\dots01\dots\dots)_2 \\ x = (00\dots0\dots1\dots)_2 \end{matrix} $ 108 109 Now, we can surely say that $\operatorname{msb}(a \oplus x) \le \operatorname{msb}(a)$. 110 111 Thus, by performing the given operation, $\operatorname{msb}(a)$ will never increase. So, if $\operatorname{msb}(b) \gt \operatorname{msb}(a)$, the answer is $-1$. 112 113 Otherwise, we can always transform $a$ into $b$ in a constructive manner. 114 115 First, we set all bits below $\operatorname{msb}(a)$ one by one to ensure that every required bit can be manipulated. Then, for each bit that is $0$ in $b$, we unset it using an appropriate XOR operation. 116 117 By following this process, we can reach $b$ from $a$ in less than $60$ operations. 118 119 Time Complexity: $O(\log_2(a))$ per testcase. 120 121 **Implementation** 122 123 ``` 124 #include<bits/stdc++.h> 125 using namespace std; 126 127 int main(){ 128 129 int t; 130 cin >> t; 131 132 while(t--){ 133 int a, b; 134 cin >> a >> b; 135 136 if(__builtin_clz(a) > __builtin_clz(b)) cout << "-1\n"; 137 else if(a == b) cout << "0\n"; 138 else{ 139 vector<int> val; 140 for(int i = 0; i < 31; i++){ 141 int x = (1 << i); 142 if(x <= a && (a & x) == 0) a += x, val.push_back(x); 143 } 144 for(int i = 0; i < 31; i++){ 145 int x = (1 << i); 146 if(x <= a && (b & x) == 0) val.push_back(x); 147 } 148 cout << val.size() << '\n'; 149 for(auto z : val) cout << z << ' '; 150 cout << '\n'; 151 } 152 } 153 } 154 ``` 155 156 [2162D - Красивая перестановка](/contest/2162/problem/D "Codeforces Round 1059 (Div. 3)") 157 158 Idea: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever") Preparation: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever") 159 160 **Solution** 161 162 We denote 163 164 $ \operatorname{query}(1, l, r) = p_l + p_{l + 1} \dots + p_r $ $ \operatorname{query}(2, l, r) = a_l + a_{l + 1} \dots + a_r $ 165 166 Now, let us try to find $l$ first. 167 168 Consider two additional arrays representing the prefix sums of the arrays $p$ and $a$, defined as follows: 169 170 $ \mathrm{pref\_sum\_p}[i] = p_1 + p_2 + \dots + p_i, \quad 1 \le i \le n $ $ \mathrm{pref\_sum\_a}[i] = a_1 + a_2 + \dots + a_i, \quad 1 \le i \le n $ 171 172 Analysing these, we can say that $\text{pref_sum_a}[i] \ge \text{pref_sum_p}[i]$ for all $i$. In fact, the inequality holds true only when $l \le i \le n$. 173 174 Thus, we can binary search for $l$. 175 176 At each stage, we make $2$ queries $\operatorname{query}(1, 1, \text{mid})$ and $\operatorname{query}(2, 1, \text{mid})$, and by comparing these, we can adjust $\text{left}$ and $\text{right}$ in binary search. 177 178 We can also find $r$ by querying suffixes in a similar way, but that would take a total of $4 \cdot \lceil \log_2(n) \rceil$ queries. This exceeds the query limit. 179 180 Instead, we can query the whole array once and find $r$. In other words, 181 182 $ \operatorname{query}(2, 1, n) - \operatorname{query}(1, 1, n) = r - l + 1 $ 183 184 So, after finding $l$, we can find $r$ in $2$ queries. Total queries will be equal to $2 \cdot \lceil \log_2(n) \rceil + 2$ ($ \lt 40$). 185 186 Time Complexity: $O(\log_2(n))$ per testcase. 187 188 **Implementation** 189 190 ``` 191 #include<bits/stdc++.h> 192 using namespace std; 193 194 #define ll long long 195 196 ll query(int type, int l, int r){ 197 ll x; 198 cout << type << ' ' << l << ' ' << r << flush << endl; 199 cin >> x; 200 return x; 201 } 202 203 int main(){ 204 205 int t; 206 cin >> t; 207 208 while(t--){ 209 210 int n; 211 cin >> n; 212 213 ll sum = query(2, 1, n); 214 sum -= ((n * (n + 1)) / 2); 215 216 ll diff = sum - 1; 217 218 int l = 1, r = n; 219 220 while(l < r){ 221 int md = (l + r) / 2; 222 ll val1 = query(1, 1, md); 223 ll val2 = query(2, 1, md); 224 225 if(val1 < val2) r = md; 226 else l = md + 1; 227 } 228 229 cout << "!" << ' ' << l << ' ' << diff + l << flush << endl; 230 231 } 232 } 233 ``` 234 235 [2162E - Красивые палиндромы](/contest/2162/problem/E "Codeforces Round 1059 (Div. 3)") 236 237 Idea: [wuhudsm](/profile/wuhudsm "Мастер wuhudsm") Preparation: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever") 238 239 **Solution** 240 241 Instead of carefully choosing all $k$ elements individually, it is sufficient to pick **three distinct integers** $x$, $y$, and $z$ and repeat them cyclically — that is, append 242 243 $x, y, z, x, y, z, \dots$ 244 245 until we perform $k$ operations. For $n \ge 3$, we can always find such $x$, $y$, $z$ that add no extra palindromic subarrays. 246 247 Now let's try to find such integers $x$, $y$, $z$. There will be two cases. 248 249 **Case 1**: $a$ is a permutation of ${1,2,3, \dots ,n}$. 250 251 If the array $a$ is a permutation, we can simply choose the first three elements of $a$ for the construction. That is, let $x = a_1$, $y = a_2$, and $z = a_3$. Since all elements in a permutation are distinct, these choices guarantee that $x$, $y$, and $z$ are distinct and add no extra palindromic subarrays. 252 253 **Case 2**: $a$ is not a permutation of ${1,2,3, \dots ,n}$. 254 255 If the array $a$ is not a permutation, we can choose $x$ to be any integer that does not appear in $a$. Let $z$ be the last element of the array, and choose $y$ as any integer different from both $x$ and $z$. These three numbers will always be distinct and add no extra palindromic subarrays. 256 257 Time Complexity: $O(n + k)$ per testcase. 258 259 **Implementation** 260 261 ``` 262 #include<bits/stdc++.h> 263 using namespace std; 264 265 int main(){ 266 267 int t; 268 cin >> t; 269 270 while(t--){ 271 272 int n, k; 273 cin >> n >> k; 274 275 vector<int> a(n), cnt(n + 1, 0); 276 for(int i = 0; i < n; i++) cin >> a[i], cnt[a[i]]++; 277 278 int x = -1; 279 for(int i = 1; i <= n; i++) if(cnt[i] == 0){ 280 x = i; 281 break; 282 } 283 284 if(x == -1){ 285 for(int i = 0; i < k; i++) cout << a[n - 3 + (i % 3)] << ' '; 286 cout << '\n'; 287 } 288 else{ 289 int y = -1; 290 for(int i = 1; i <= n; i++) if(i != x && i != a[n - 1]){ 291 y = i; 292 break; 293 } 294 vector<int> v = {x, y, a[n - 1]}; 295 for(int i = 0; i < k; i++) cout << v[i % 3] << ' '; 296 cout << '\n'; 297 } 298 299 } 300 } 301 ``` 302 303 [2162F - Красивые отрезки](/contest/2162/problem/F "Codeforces Round 1059 (Div. 3)") 304 305 Idea: [frostcat](/profile/frostcat "Новичок frostcat"), [wuhudsm](/profile/wuhudsm "Мастер wuhudsm"), [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever") Preparation: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever") 306 307 **Solution** 308 309 Note that if $[0,2,1]$ is a subsequence of permutation $p$, any interval that includes $0$ and $1$ must also include $2$. This implies that $\operatorname{mex}$ of any interval will not be equal to $2$. So, $2 \notin M$. Hence, $\operatorname{mex}(M) \le 2$. 310 311 Thus, we can always ensure that $\operatorname{mex}(M) \le 2$. Now, we only need to check when $\operatorname{mex}(M) = 0$ and $\operatorname{mex}(M) = 1$ are possible. 312 313 For $\operatorname{mex}(M)$ to be equal to $0$, $\operatorname{mex}$ of every interval must be positive. So, every interval must include $0$. This is possible only when all intervals intersect at a common point — that is, there exists at least one point that lies within every interval. Then we place $0$ at some common point and fill the remaining permutation. 314 315 Otherwise, for $\operatorname{mex}(M)$ to be equal to $1$, $\operatorname{mex}$ of each interval must not be equal to $1$. To ensure this, we have to place $0$ and $1$ in such a way that if an interval includes $0$, it must also include $1$. This is possible if there exists a point that is not simultaneously the starting point of one interval and the ending point of another. In other words, we should be able to find a position that does not act as both a left and a right boundary. Then we place $0$ at such a point and $1$ adjacent to it. 316 317 Else, we place $[0,2,1]$ as a subsequence first and then build the remaining permutation. 318 319 Time Complexity: $O(n + m)$ per testcase. 320 321 **Implementation** 322 323 ``` 324 #include <bits/stdc++.h> 325 using namespace std; 326 #define int long long 327 #define INF (int)1e18 328 329 void Solve() 330 { 331 332 int n, m; cin >> n >> m; 333 334 vector <int> l(m), r(m), f(n + 1), st(n + 1, 0), en(n + 1); 335 for (int i = 0; i < m; i++){ 336 cin >> l[i] >> r[i]; 337 st[l[i]] = 1; 338 en[r[i]] = 1; 339 for (int j = l[i]; j <= r[i]; j++){ 340 f[j]++; 341 } 342 } 343 344 vector <int> ans(n + 1, -1); 345 346 auto fill = [&](){ 347 vector <bool> used(n, false); 348 for (int i = 1; i <= n; i++) if (ans[i] != -1) used[ans[i]] = true; 349 350 int p = 0; 351 for (int i = 1; i <= n; i++){ 352 if (ans[i] == -1){ 353 while (used[p]) p++; 354 355 ans[i] = p; 356 used[p] = true; 357 } 358 } 359 360 for (int i = 1; i <= n; i++){ 361 cout << ans[i] << " \n"[i == n]; 362 } 363 }; 364 365 for (int i = 1; i <= n; i++){ 366 if (f[i] == m){ 367 int ptr = 1; 368 ans[i] = 0; 369 370 fill(); 371 return; 372 } 373 } 374 375 for (int i = 1; i < n; i++){ 376 if (en[i] == 0){ 377 ans[i] = 0; 378 ans[i + 1] = 1; 379 fill(); 380 return; 381 } 382 383 if (st[i + 1] == 0){ 384 ans[i] = 1; 385 ans[i + 1] = 0; 386 fill(); 387 return; 388 } 389 } 390 391 assert(n >= 3); 392 ans[1] = 0; 393 ans[2] = 2; 394 ans[3] = 1; 395 396 fill(); 397 } 398 399 int32_t main() 400 { 401 ios_base::sync_with_stdio(0); 402 cin.tie(0); 403 int t = 1; 404 cin >> t; 405 for(int i = 1; i <= t; i++) 406 { 407 Solve(); 408 } 409 410 return 0; 411 } 412 ``` 413 414 [2162G - Красивое дерево](/contest/2162/problem/G "Codeforces Round 1059 (Div. 3)") 415 416 Idea: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever") Preparation: [wakanda-forever](/profile/wakanda-forever "Эксперт wakanda-forever") 417 418 **Solution** 419 420 We have to construct a tree with $n$ vertices such that $S = \sum_{{u, v} \in E} (u \cdot v)$ is a perfect square. 421 422 Instead of making it any random perfect square, let's try to make $S = (f(n))^2$ where $f(n)$ is an integer function of $n$. 423 424 Now, let's check if we can make $f(n) = n$. For $n = 5$, we can consider the following tree 425 426 $5-1-2-3-4$ 427 428 where $S = 25 = (5)^2$. 429 430 Now that we know we have a tree $T$ with $n$ ($=5$) vertices having $S = n^2$. Using this, let's try to make a tree $T'$ with $n + 1$ vertices such that $S' = (n + 1)^2$. Note that $S' - S = 2n + 1$. So, while constructing $T'$, we have to add a new vertex $(n + 1)$ and also adjust this extra sum $2n + 1$. 431 432 We can achieve this in the following manner: 433 434 * add an edge between $1$ and $n + 1$, 435 * remove the edge between $1$ and $n$, 436 * add an edge between $2$ and $n$. 437 438 This analogy can be extended for all $n \ge 5$. Such trees have the following structure: 439 440  441 442 So, we can always make $S = n^2$ for all $n \ge 5$. For $n \lt 5$, we can just print sample outputs. 443 444 One can also assume $f(n) = n + 1$ and construct a similar solution with $S = (n + 1)^2$. 445 446 Time Complexity: $O(n)$ per testcase. 447 448 **Implementation** 449 450 ``` 451 #include<bits/stdc++.h> 452 using namespace std; 453 454 int main(){ 455 456 int t; 457 cin >> t; 458 459 while(t--){ 460 461 int n; 462 cin >> n; 463 464 if(n == 2){ 465 cout << -1 << '\n'; 466 continue; 467 } 468 469 if(n == 3){ 470 cout << "1 3\n2 3\n"; 471 continue; 472 } 473 474 if(n == 4){ 475 cout << "1 2\n3 1\n4 1\n"; 476 continue; 477 } 478 479 cout << "1 2\n"; 480 cout << "2 3\n"; 481 cout << "3 4\n"; 482 483 cout << "1 " << n << '\n'; 484 485 for(int i = 5; i < n; i++) cout << 2 << ' ' << i << '\n'; 486 } 487 } 488 ``` 489 490 [2162H - Красивая задача](/contest/2162/problem/H "Codeforces Round 1059 (Div. 3)") 491 492 Idea: [wuhudsm](/profile/wuhudsm "Мастер wuhudsm") Preparation: [wuhudsm](/profile/wuhudsm "Мастер wuhudsm") 493 494 **Spoiler** 495 496  497 498 **Solution** 499 500 When the value of $f$ is 1 for $[l_i, r_i]$, all numbers in $[l_i, r_i]$ are either $\leq x$ or $\geq x$. 501 502 We observe that for each interval, we need to divide the intervals into S-intervals (smaller) and B-intervals (bigger). S-intervals can only contain numbers $\leq x$, and B-intervals can only contain numbers $\geq x$. 503 504 Assuming we have fixed the S-intervals and B-intervals. For each index $i$, there are 4 types: 505 506 * Type 1: $i$ is covered only by S-intervals; 507 * Type 2: $i$ is covered only by B-intervals; 508 * Type 3: $i$ is covered by both S-intervals and B-intervals; 509 * Type 4: $i$ is covered by neither S-intervals nor B-intervals. 510 511 Let $cnt_s$ be the number of values $ \lt x$, and $cnt_b$ be the number of values $ \gt x$. 512 513 When there are no type 4 indices, we only need to check whether: 514 515 * $cnt_s \leq$ (total number of type 1 indices) 516 * $cnt_b \leq$ (total number of type 2 indices) 517 518 When type 4 indices exist, we only need to make a slight modification to the condition (this modification is left to the reader). 519 520 Consider a simpler case: all intervals are non-overlapping. In this case, the problem reduces to a classic knapsack problem, where each interval becomes an independent item. We consider extending the idea of DP to the original problem. 521 522 We find that intervals that are contained within others are useless and can be removed. Then, the intervals can be sorted by their left endpoints. This way, for $i \lt j$, we can ensure $l_i \lt l_j$ and $r_i \lt r_j$. Then, we perform DP based on the order of the intervals. 523 524 We define: 525 526 $dp[i][j][k = 0 \text{ or } 1]$: For the first $i$ intervals, the total number of type 1 indices is $j$, and the last interval is an S-interval ($k = 0$) or a B-interval ($k = 1$), the maximum total number of type 2 indices obtained. 527 528 Let $inslen[i]$ be the length of the intersection between the $i$-th interval and the $(i-1)$-th interval. 529 530 Transitions: 531 532 * $dp[i][j][0] = \max(dp[i-1][j - inslen[i]][0], dp[i-1][j - inslen[i]][1] - inslen[i])$ 533 * $dp[i][j][1] = \max(dp[i-1][j][1] + inslen[i], dp[i-1][j + inslen[i]][1] + inslen[i])$ 534 535 Note: For intervals $(i-2)$, $(i-1)$, $i$, if the type of interval $(i-1)$ is different from both $(i-2)$ and $i$, and $r[i-2] \geq l[i]$, some overlapping parts may be subtracted repeatedly. However, we find that this does not affect the final answer because it is not better than the answer when all three intervals are of the same type. Here, a common DP idea is applied: if "incorrect" states are recorded but they cannot be optimal, the DP transitions can remain unchanged (a similar idea is used in: <https://codeforces.com/contest/1859/problem/E)>. 536 537 | State 1 | State 2 | 538 | --- | --- | 539 | 2025-10-18 064710.png) | 2025-10-18 064836.png | 540 | Some overlapping parts (in the middle) are subtracted repeatedly. | Better because the value range of the middle positions is strictly larger. | 541 542 Afterward, answering queries using the DP array is trivial. The time complexity is $O(n^2)$. 543 544 --- 545 546 There is another DP approach. Let $b[i]$ be the smallest $j \leq i$ such that $j$ and $i$ are covered by the same interval. Then, if position $i$ is filled with a number $ \lt x$, we can deduce that all numbers in $a'[b[i], \ldots, i]$ must be $ \lt x$, and so on. This way, we can write a DP that transitions position by position, without pre-processing each interval. 547 548 For details, refer to [Dominater069](/profile/Dominater069 "Легендарный гроссмейстер Dominater069") 's code. 549 550 **Implementation1(wuhudsm)** 551 552 ``` 553 #include <map> 554 #include <set> 555 #include <cmath> 556 #include <ctime> 557 #include <queue> 558 #include <stack> 559 #include <cstdio> 560 #include <cstdlib> 561 #include <vector> 562 #include <cstring> 563 #include <algorithm> 564 #include <iostream> 565 #include <bitset> 566 #include <unordered_map> 567 #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 568 using namespace std; 569 typedef double db; 570 typedef long long ll; 571 typedef unsigned long long ull; 572 const int N=3010; 573 const int LOGN=28; 574 const ll TMD=0; 575 const ll INF=100000000; 576 int T,n,m; 577 int a[N],cnt[N],mxr[N]; 578 int dp[N][N][2]; 579 580 /* 581 * stuff you should look for 582 * [Before Submission] 583 * array bounds, initialization, int overflow, special cases (like n=1), typo 584 * [Still WA] 585 * check typo carefully 586 * casework mistake 587 * special bug 588 * stress test 589 */ 590 591 //-------------------------------------------------------------------------- 592 593 struct seg 594 { 595 int l,r; 596 597 seg() {} 598 599 seg(int l,int r):l(l),r(r){} 600 601 int len() 602 { 603 return r-l+1; 604 } 605 }; 606 607 seg getins(seg x,seg y) 608 { 609 if(x.l>y.l) swap(x,y); 610 if(x.r<y.l) return seg(INF,INF); 611 if(x.r<y.r) return seg(y.l,x.r); 612 else return seg(y.l,y.r); 613 } 614 615 //-------------------------------------------------------------------------- 616 617 void init() 618 { 619 cin>>n>>m; 620 for(int i=0;i<=n;i++) 621 mxr[i]=0; 622 for(int i=1;i<=n;i++) 623 cin>>a[i]; 624 for(int i=1;i<=m;i++) 625 { 626 int l,r; 627 cin>>l>>r; 628 mxr[l]=max(mxr[l],r); 629 } 630 for(int i=0;i<=n+4;i++) 631 for(int j=0;j<=n+4;j++) 632 dp[i][j][0]=dp[i][j][1]=-INF; 633 } 634 635 void solve() 636 { 637 int sz,cfree=0; 638 vector<int> tag(n+4); 639 vector<seg> vs; 640 for(int i=1;i<=n;i++) 641 { 642 if(!mxr[i]) continue; 643 if(vs.empty()||vs.back().r<mxr[i]) 644 vs.push_back(seg(i,mxr[i])); 645 } 646 sz=vs.size(); 647 dp[1][0][0]=vs[0].len(); 648 dp[1][vs[0].len()][1]=0; 649 for(int i=2;i<=sz;i++) 650 { 651 seg cur=vs[i-1],ins=getins(vs[i-2],vs[i-1]); 652 int len_ins=(ins.l==INF?0:ins.len()); 653 for(int j=0;j<=n;j++) 654 { 655 dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][0]+cur.len()-len_ins); 656 if(j+len_ins<=n) 657 dp[i][j][0]=max(dp[i][j][0],dp[i-1][j+len_ins][1]+cur.len()-len_ins); 658 if(j-(cur.len()-len_ins)>=0) 659 { 660 dp[i][j][1]=max(dp[i][j][1],dp[i-1][j-(cur.len()-len_ins)][1]); 661 dp[i][j][1]=max(dp[i][j][1],dp[i-1][j-(cur.len()-len_ins)][0]-len_ins); 662 } 663 } 664 } 665 for(int i=0;i<vs.size();i++) 666 for(int j=vs[i].l;j<=vs[i].r;j++) 667 tag[j]=1; 668 for(int i=1;i<=n;i++) 669 if(!tag[i]) cfree++; 670 for(int i=1;i<=n;i++) 671 { 672 int s=0,b=0; 673 for(int j=1;j<=n;j++) 674 { 675 if(a[j]<i) s++; 676 else if(a[j]>i) b++; 677 } 678 int flg=0; 679 for(int j=0;j<=n;j++) 680 { 681 int need1=max(0,s-j),need2=max(0,b-max(dp[sz][j][0],dp[sz][j][1])); 682 flg|=(cfree>=need1+need2); 683 } 684 cout<<flg; 685 } 686 cout<<"\n"; 687 } 688 689 //------------------------------------------------------- 690 691 void gen_data() 692 { 693 srand(time(NULL)); 694 } 695 696 int bruteforce() 697 { 698 return 0; 699 } 700 701 //------------------------------------------------------- 702 703 int main() 704 { 705 fastio; 706 707 cin>>T; 708 while(T--) 709 { 710 init(); 711 solve(); 712 713 /* 714 715 //Stress Test 716 717 gen_data(); 718 auto ans1=solve(),ans2=bruteforce(); 719 if(ans1==ans2) printf("OK!\n"); 720 else 721 { 722 //Output Data 723 } 724 725 */ 726 } 727 728 return 0; 729 } 730 ``` 731 732 **Implementation2 (Dominater069)** 733 734 ``` 735 #include <bits/stdc++.h> 736 using namespace std; 737 #define INF (int)1e9 738 739 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); 740 741 void Solve() 742 { 743 // x <= min or x >= max 744 // min < x < max is bad 745 // => in range if both smaller and larger exists, cooked 746 // just spam smaller at one end, and larger at other end? 747 // i <-> j if there exists interval covering both 748 // if i <-> j, cannot have diff type on i and j 749 // dp[i][number of 0s] = max number of 1s, but also need to know what is the last 0 / 1 position 750 // we can extend last character always 751 // we can extend other character only after some gap 752 // prefmax? 753 754 int n, m; cin >> n >> m; 755 756 vector <int> a(n + 1), f(n + 1); 757 for (int i = 1; i <= n; i++){ 758 cin >> a[i]; 759 f[a[i]]++; 760 } 761 762 vector <int> b(n + 1), c(n + 1); 763 for (int i = 1; i <= n; i++){ 764 b[i] = c[i] = i; 765 } 766 for (int i = 1; i <= m; i++){ 767 int l, r; cin >> l >> r; 768 for (int j = l; j <= r; j++){ 769 b[j] = min(b[j], l); 770 c[j] = max(c[j], r); 771 } 772 } 773 774 // vector dp(n + 1, vector(n + 1, vector <int>(2, -INF))); 775 // vector pref(n + 1, vector(n + 1, vector <int>(2, -INF))); 776 int dp[n + 1][n + 1][2]; 777 int pref[n + 1][n + 1][2]; 778 779 for (int i = 0; i <= n; i++){ 780 for (int j = 0; j <= n; j++){ 781 for (int k = 0; k < 2; k++){ 782 dp[i][j][k] = -INF; 783 pref[i][j][k] = -INF; 784 } 785 } 786 } 787 788 dp[0][0][0] = dp[0][0][1] = 0; 789 pref[0][0][0] = pref[0][0][1] = 0; 790 791 for (int i = 1; i <= n; i++){ 792 for (int x = 0; x <= n; x++){ 793 for (int y = 0; y < 2; y++){ 794 for (int z = 0; z < 2; z++){ 795 if (y == z){ 796 int px = x - (y == 0); 797 if (px >= 0){ 798 dp[i][x][y] = max(dp[i][x][y], pref[i - 1][px][z] + (y == 1)); 799 } 800 } else { 801 int px = x - (y == 0); 802 int lim = b[i] - 1; 803 if (px >= 0){ 804 dp[i][x][y] = max(dp[i][x][y], pref[lim][px][z] + (y == 1)); 805 } 806 } 807 } 808 809 pref[i][x][y] = max(pref[i - 1][x][y], dp[i][x][y]); 810 } 811 } 812 } 813 814 for (int i = 1; i <= n; i++){ 815 int lower = 0; 816 int upper = 0; 817 for (int j = 1; j < i; j++) lower += f[j]; 818 for (int j = i + 1; j <= n; j++) upper += f[j]; 819 820 if (pref[n][lower][0] >= upper || pref[n][lower][1] >= upper){ 821 cout << "1"; 822 } else { 823 cout << "0"; 824 } 825 } 826 cout << "\n"; 827 } 828 829 int32_t main() 830 { 831 auto begin = std::chrono::high_resolution_clock::now(); 832 ios_base::sync_with_stdio(0); 833 cin.tie(0); 834 int t = 1; 835 // freopen("in", "r", stdin); 836 // freopen("out", "w", stdout); 837 838 cin >> t; 839 for(int i = 1; i <= t; i++) 840 { 841 //cout << "Case #" << i << ": "; 842 Solve(); 843 } 844 auto end = std::chrono::high_resolution_clock::now(); 845 auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); 846 cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 847 return 0; 848 } 849 ```