1417.md (20410B)
1 Source: https://codeforces.com/blog/entry/83036 2 3 *Several unexpected Kuhn solutions passed for D1F. Could you please discuss your solutions in the comments and prove its correctness or provide any counter-examples. Author's solution uses flows with Dinic.* 4 5 Editorial is not completed yet. Problem D1F will be added later. Hope you enjoyed the problemset! 6 7 Editorial was/will be written by [bthero](/profile/bthero "Master bthero") and [BledDest](/profile/BledDest "International Grandmaster BledDest"). 8 9 Our tester [namanbansal013](/profile/namanbansal013 "Expert namanbansal013") has made amazing video-tutorials on YouTube for problems [D2D/D1B](https://youtu.be/LS51ijnR8jI) and [D2E/D1C](https://youtu.be/rBSuG-_R3Yo). Make sure to check them out and show him some love! 10 11 Finally added the editorial for D1E. Currently it is very complicated and error-prone. 12 13 Div2A by [bthero](/profile/bthero "Master bthero") 14 15 **Editorial** 16 17 Tutorial is loading... 18 19 **Code in C++ (BThero)** 20 21 ``` 22 // chrono::system_clock::now().time_since_epoch().count() 23 #include<bits/stdc++.h> 24 25 #define pb push_back 26 #define eb emplace_back 27 #define mp make_pair 28 #define fi first 29 #define se second 30 #define all(x) (x).begin(), (x).end() 31 #define debug(x) cerr << #x << " = " << x << endl; 32 33 using namespace std; 34 35 typedef long long ll; 36 typedef pair<int, int> pii; 37 38 const int MAXN = (int)1e3 + 5; 39 40 int n, k; 41 int arr[MAXN]; 42 43 void solve() { 44 scanf("%d %d", &n, &k); 45 46 for (int i = 1; i <= n; ++i) { 47 scanf("%d", &arr[i]); 48 } 49 50 int mn = min_element(arr + 1, arr + n + 1) - arr; 51 int ans = 0; 52 53 for (int i = 1; i <= n; ++i) { 54 if (i != mn) { 55 while (arr[i] + arr[mn] <= k) { 56 arr[i] += arr[mn]; 57 ++ans; 58 } 59 } 60 } 61 62 printf("%d\n", ans); 63 } 64 65 int main() { 66 int tt; 67 scanf("%d", &tt); 68 69 while (tt--) { 70 solve(); 71 } 72 73 return 0; 74 } 75 ``` 76 77 Div2B by [nkamzabek](/profile/nkamzabek "Expert nkamzabek") 78 79 **Editorial** 80 81 Tutorial is loading... 82 83 **Code in C++ (hugopm)** 84 85 ``` 86 #include <bits/stdc++.h> 87 #define len(v) ((int)((v).size())) 88 #define all(v) (v).begin(), (v).end() 89 #define rall(v) (v).rbegin(), (v).rend() 90 #define chmax(x, v) x = max((x), (v)) 91 #define chmin(x, v) x = min((x), (v)) 92 using namespace std; 93 using ll = long long; 94 95 void solve() { 96 int n, tar; 97 cin >> n >> tar; 98 int curMid = 0; 99 for (int i = 0; i < n; ++i) { 100 int x; cin >> x; 101 int r; 102 if (tar % 2 == 0 && x == tar/2) 103 r = (curMid++) % 2; 104 else if (2*x < tar) 105 r = 0; 106 else 107 r = 1; 108 cout << r << " \n"[i==n-1]; 109 } 110 } 111 112 int main() { 113 ios::sync_with_stdio(false), cin.tie(0); 114 115 int nbTests; 116 cin >> nbTests; 117 for (int iTest = 0; iTest < nbTests; ++iTest) { 118 solve(); 119 } 120 } 121 ``` 122 123 Div2C/Div1A by [nkamzabek](/profile/nkamzabek "Expert nkamzabek") 124 125 **Editorial** 126 127 Tutorial is loading... 128 129 **Code in C++ (BThero)** 130 131 ``` 132 // chrono::system_clock::now().time_since_epoch().count() 133 #include<bits/stdc++.h> 134 135 #define pb push_back 136 #define eb emplace_back 137 #define mp make_pair 138 #define fi first 139 #define se second 140 #define all(x) (x).begin(), (x).end() 141 #define debug(x) cerr << #x << " = " << x << endl; 142 143 using namespace std; 144 145 typedef long long ll; 146 typedef pair<int, int> pii; 147 148 const int MAXN = (int)3e5 + 5; 149 150 int f[MAXN], last[MAXN], arr[MAXN], ans[MAXN]; 151 int n; 152 153 void solve() { 154 scanf("%d", &n); 155 156 for (int i = 1; i <= n; ++i) { 157 f[i] = last[i] = 0; 158 ans[i] = -1; 159 } 160 161 for (int i = 1; i <= n; ++i) { 162 scanf("%d", &arr[i]); 163 } 164 165 for (int i = 1; i <= n; ++i) { 166 int x = arr[i]; 167 f[x] = max(f[x], i - last[x]); 168 last[x] = i; 169 } 170 171 for (int x = 1; x <= n; ++x) { 172 f[x] = max(f[x], n - last[x] + 1); 173 174 for (int i = f[x]; i <= n && ans[i] == -1; ++i) { 175 ans[i] = x; 176 } 177 } 178 179 for (int i = 1; i <= n; ++i) { 180 printf("%d%c", ans[i], " \n"[i == n]); 181 } 182 } 183 184 int main() { 185 int tt; 186 scanf("%d", &tt); 187 188 while (tt--) { 189 solve(); 190 } 191 192 return 0; 193 } 194 ``` 195 196 Div2D/Div1B by [nkamzabek](/profile/nkamzabek "Expert nkamzabek") 197 198 **Editorial** 199 200 Tutorial is loading... 201 202 **Code in C++ (BThero)** 203 204 ``` 205 // chrono::system_clock::now().time_since_epoch().count() 206 #include<bits/stdc++.h> 207 208 #define pb push_back 209 #define eb emplace_back 210 #define mp make_pair 211 #define fi first 212 #define se second 213 #define all(x) (x).begin(), (x).end() 214 #define debug(x) cerr << #x << " = " << x << endl; 215 216 using namespace std; 217 218 typedef long long ll; 219 typedef pair<int, int> pii; 220 221 const int MAXN = (int)1e4 + 5; 222 223 vector<array<int, 3>> ans; 224 int arr[MAXN]; 225 int n; 226 227 void go(int x, int y, int z) { 228 arr[x] -= x * z; 229 arr[y] += x * z; 230 ans.pb({x, y, z}); 231 } 232 233 void solve() { 234 scanf("%d", &n); 235 236 for (int i = 1; i <= n; ++i) { 237 scanf("%d", &arr[i]); 238 } 239 240 ans.clear(); 241 int sum = accumulate(arr + 1, arr + n + 1, 0); 242 243 if (sum % n) { 244 printf("-1\n"); 245 return; 246 } 247 248 for (int i = 2; i <= n; ++i) { 249 if (arr[i] % i) { 250 go(1, i, i - arr[i] % i); 251 } 252 253 go(i, 1, arr[i] / i); 254 } 255 256 for (int i = 2; i <= n; ++i) { 257 go(1, i, sum / n); 258 } 259 260 for (int i = 1; i <= n; ++i) { 261 assert(arr[i] == sum / n); 262 } 263 264 assert((int)ans.size() <= 3 * n); 265 printf("%d\n", (int)ans.size()); 266 267 for (auto &[x, y, z] : ans) { 268 printf("%d %d %d\n", x, y, z); 269 } 270 } 271 272 int main() { 273 int tt; 274 scanf("%d", &tt); 275 276 while (tt--) { 277 solve(); 278 } 279 280 return 0; 281 } 282 ``` 283 284 Div2E/Div1C by [DimmyT](/profile/DimmyT "Master DimmyT") 285 286 **Editorial** 287 288 Tutorial is loading... 289 290 **Code in C++ (RedDreamer)** 291 292 ``` 293 #include <bits/stdc++.h> 294 295 #define mp make_pair 296 #define pb push_back 297 #define f first 298 #define s second 299 #define ll long long 300 #define forn(i, a, b) for(int i = (a); i <= (b); ++i) 301 #define forev(i, b, a) for(int i = (b); i >= (a); --i) 302 #define VAR(v, i) __typeof( i) v=(i) 303 #define forit(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) 304 #define all(x) (x).begin(), (x).end() 305 #define sz(x) ((int)(x).size()) 306 #define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout); 307 308 using namespace std; 309 310 const int maxn = (int)5e6 + 100; 311 const int maxm = (int)1e6 + 100; 312 const int mod = (int)1e9 + 7; 313 const int P = (int) 1e6 + 7; 314 const double pi = acos(-1.0); 315 316 #define inf mod 317 318 typedef long double ld; 319 typedef pair<int, int> pii; 320 typedef pair<ll, ll> pll; 321 typedef vector<int> vi; 322 typedef vector<ll> Vll; 323 typedef vector<pair<int, int> > vpii; 324 typedef vector<pair<ll, ll> > vpll; 325 326 int n, t[2][maxn], id = 1; 327 ll dp[2][30]; 328 vi g[maxn]; 329 330 void add(int x, int pos){ 331 int v = 0; 332 forev(i, 29, 0){ 333 int bit = ((x >> i) & 1); 334 if(!t[bit][v]) t[bit][v] = id++; 335 v = t[bit][v]; 336 g[v].pb(pos); 337 } 338 } 339 void go(int v, int b = 29){ 340 int l = t[0][v], r = t[1][v]; 341 if(l) go(l, b - 1); 342 if(r) go(r, b - 1); 343 if(!l || !r) return; 344 ll res = 0; 345 int ptr = 0; 346 for(auto x : g[l]){ 347 while(ptr < sz(g[r]) && g[r][ptr] < x) ptr++; 348 res += ptr; 349 } 350 dp[0][b] += res; 351 dp[1][b] += sz(g[l]) * 1ll * sz(g[r]) - res; 352 } 353 void solve(){ 354 scanf("%d", &n); 355 forn(i, 1, n){ 356 int x; 357 scanf("%d", &x); 358 add(x, i); 359 } 360 go(0); 361 ll inv = 0; 362 int res = 0; 363 forn(i, 0, 29){ 364 inv += min(dp[0][i], dp[1][i]); 365 if(dp[1][i] < dp[0][i]) 366 res += (1 << i); 367 } 368 printf("%lld %d", inv, res); 369 } 370 371 int main () { 372 int t = 1; 373 //scanf("%d", &t); 374 while(t--) solve(); 375 } 376 ``` 377 378 Div2F/Div1D by [DimmyT](/profile/DimmyT "Master DimmyT") 379 380 **Editorial** 381 382 Tutorial is loading... 383 384 **Code in C++ (BThero)** 385 386 ``` 387 // chrono::system_clock::now().time_since_epoch().count() 388 #include<bits/stdc++.h> 389 390 #define pb push_back 391 #define eb emplace_back 392 #define mp make_pair 393 #define fi first 394 #define se second 395 #define all(x) (x).begin(), (x).end() 396 #define debug(x) cerr << #x << " = " << x << endl; 397 398 using namespace std; 399 400 typedef long long ll; 401 typedef pair<int, int> pii; 402 403 const int MAXN = (int)5e5 + 5; 404 const int MAXM = (int)3e5 + 5; 405 const int MAXQ = (int)5e5 + 5; 406 407 pii e[MAXM], que[MAXQ], t[MAXN << 2]; 408 vector<int> adj[MAXN]; 409 int tin[MAXN], tout[MAXN], timer; 410 int par[MAXN], arr[MAXN]; 411 bool del[MAXM]; 412 int n, m, q; 413 414 int getPar(int x) { 415 if (x == par[x]) { 416 return x; 417 } 418 419 return par[x] = getPar(par[x]); 420 } 421 422 void uni(int a, int b) { 423 a = getPar(a); 424 b = getPar(b); 425 426 if (a == b) { 427 return; 428 } 429 430 ++n; 431 par[n] = n; 432 par[a] = n; 433 par[b] = n; 434 adj[n].pb(a); 435 adj[n].pb(b); 436 } 437 438 void dfs(int v) { 439 tin[v] = ++timer; 440 441 for (int to : adj[v]) { 442 dfs(to); 443 } 444 445 tout[v] = timer; 446 } 447 448 pii segMax(int v, int tl, int tr, int l, int r) { 449 if (l > r || tl > r || tr < l) { 450 return mp(0, 0); 451 } 452 453 if (l <= tl && tr <= r) { 454 return t[v]; 455 } 456 457 int mid = (tl + tr) >> 1; 458 int c1 = (v << 1), c2 = (c1 | 1); 459 460 return max(segMax(c1, tl, mid, l, r), segMax(c2, mid + 1, tr, l, r)); 461 } 462 463 void updPos(int v, int tl, int tr, int p, pii x) { 464 if (tl == tr) { 465 t[v] = x; 466 return; 467 } 468 469 int mid = (tl + tr) >> 1; 470 int c1 = (v << 1), c2 = (c1 | 1); 471 472 if (p <= mid) { 473 updPos(c1, tl, mid, p, x); 474 } 475 else { 476 updPos(c2, mid + 1, tr, p, x); 477 } 478 479 t[v] = max(t[c1], t[c2]); 480 } 481 482 void solve() { 483 scanf("%d %d %d", &n, &m, &q); 484 485 for (int i = 1; i <= n; ++i) { 486 scanf("%d", &arr[i]); 487 } 488 489 for (int i = 1; i <= m; ++i) { 490 int u, v; 491 scanf("%d %d", &u, &v); 492 e[i] = mp(u, v); 493 } 494 495 for (int i = 1; i <= q; ++i) { 496 int a, b; 497 scanf("%d %d", &a, &b); 498 que[i] = mp(a, b); 499 500 if (a == 2) { 501 del[b] = 1; 502 } 503 } 504 505 for (int i = 1; i <= n; ++i) { 506 par[i] = i; 507 } 508 509 for (int i = 1; i <= m; ++i) { 510 if (!del[i]) { 511 uni(e[i].fi, e[i].se); 512 } 513 } 514 515 for (int i = q; i > 0; --i) { 516 int tp = que[i].fi; 517 518 if (tp == 2) { 519 int id = que[i].se; 520 uni(e[id].fi, e[id].se); 521 } 522 else { 523 que[i].se = getPar(que[i].se); 524 } 525 } 526 527 for (int i = 1; i <= n; ++i) { 528 if (getPar(i) == i) { 529 dfs(i); 530 } 531 } 532 533 for (int i = 1; i <= n; ++i) { 534 updPos(1, 1, n, tin[i], mp(arr[i], tin[i])); 535 } 536 537 for (int i = 1; i <= q; ++i) { 538 int tp = que[i].fi; 539 540 if (tp == 1) { 541 int v = que[i].se; 542 pii tmp = segMax(1, 1, n, tin[v], tout[v]); 543 544 if (tmp.fi == 0) { 545 printf("0\n"); 546 } 547 else { 548 printf("%d\n", tmp.fi); 549 updPos(1, 1, n, tmp.se, mp(0, 0)); 550 } 551 } 552 } 553 } 554 555 int main() { 556 int tt = 1; 557 558 while (tt--) { 559 solve(); 560 } 561 562 return 0; 563 } 564 ``` 565 566 Div1E by [bthero](/profile/bthero "Master bthero") 567 568 **Editorial** 569 570 Tutorial is loading... 571 572 **Code in C++ (BThero)** 573 574 ``` 575 // chrono::system_clock::now().time_since_epoch().count() 576 #include<bits/stdc++.h> 577 578 #define __DBG 1 579 #define pb push_back 580 #define eb emplace_back 581 #define mp make_pair 582 #define fi first 583 #define se second 584 #define all(x) (x).begin(), (x).end() 585 #define debug(x) if (__DBG) cerr << #x << " = " << x << endl; 586 587 using namespace std; 588 589 typedef long long ll; 590 typedef pair<int, int> pii; 591 typedef pair<ll, ll> pll; 592 593 const int MAXN = (int)5e5 + 5; 594 595 int arr[MAXN]; 596 int n; 597 598 void solve() { 599 scanf("%d", &n); 600 601 for (int i = 1; i <= n; ++i) { 602 scanf("%d", &arr[i]); 603 } 604 605 int zero = 0, two = -1; 606 set<pll> one; 607 ll shifter = 0; 608 int sign = 1; 609 610 for (int i = 1; i <= n; ++i) { 611 int x = arr[i]; 612 613 if (two != -1) { 614 zero += 2; 615 sign = 1; 616 shifter = 0; 617 one.clear(); 618 619 if (two < x) { 620 one.insert(mp(x - two, x - two)); 621 } 622 } 623 else if (!one.empty()) { 624 zero++; 625 626 if (sign == -1) { 627 // shifter - idx >= x 628 // shifter - x >= idx 629 // idx <= shifter - x 630 ll lim = shifter - x; 631 632 while (!one.empty() && one.begin() -> se <= lim) { 633 one.erase(one.begin()); 634 } 635 636 if (!one.empty() && one.begin() -> fi <= lim) { 637 pll it = mp(lim + 1, one.begin() -> se); 638 one.erase(one.begin()); 639 assert(it.fi <= it.se); 640 one.insert(it); 641 } 642 } 643 else { 644 // shifter + idx >= x 645 // idx >= x - shifter 646 ll lim = x - shifter; 647 648 while (!one.empty() && one.rbegin() -> fi >= lim) { 649 one.erase(--one.end()); 650 } 651 652 if (!one.empty() && one.rbegin() -> se >= lim) { 653 pll it = mp(one.rbegin() -> fi, lim - 1); 654 one.erase(--one.end()); 655 assert(it.fi <= it.se); 656 one.insert(it); 657 } 658 } 659 660 shifter = x - shifter; 661 sign *= -1; 662 } 663 else { 664 sign = -1; 665 shifter = x; 666 int lim = min(arr[i - 1] - 1, x - 1); 667 668 if (1 <= lim) { 669 one.insert(mp(1, lim)); 670 } 671 } 672 673 // consider x/2! 674 two = -1; 675 676 if (x % 2 == 0) { 677 int y = x / 2; 678 ll val = (y - shifter) / sign; 679 auto it = one.lower_bound(mp(val + 1, (ll)-1e18)); 680 bool found = 0; 681 682 if (it != one.begin()) { 683 --it; 684 685 if (it -> fi <= val && val <= it -> se) { 686 found = 1; 687 } 688 } 689 690 if (found) { 691 two = y; 692 } 693 else { 694 one.insert(mp(val, val)); 695 } 696 } 697 } 698 699 int ans; 700 701 if (two != -1) { 702 ans = zero + 2; 703 } 704 else if (!one.empty()) { 705 ans = zero + 1; 706 } 707 else { 708 ans = zero; 709 } 710 711 printf("%d\n", 2 * n - ans); 712 } 713 714 int main() { 715 int tt; 716 scanf("%d", &tt); 717 718 while (tt--) { 719 solve(); 720 } 721 722 return 0; 723 } 724 ``` 725 726 **Alternative solution code in C++ (hugopm)** 727 728 ``` 729 #include <bits/stdc++.h> 730 #define int long long 731 #define len(v) ((int)((v).size())) 732 #define all(v) (v).begin(), (v).end() 733 #define rall(v) (v).rbegin(), (v).rend() 734 #define chmax(x, v) x = max((x), (v)) 735 #define chmin(x, v) x = min((x), (v)) 736 using namespace std; 737 using pii = pair<int, int>; 738 739 struct EndSet { 740 set<int> points; 741 pii seg = {1, 0}; 742 743 int cbase = 0, cdir = 1; 744 745 void setFree(int mx) { 746 points.clear(), cbase = 0, cdir = 1; 747 seg = {1, mx}; 748 } 749 750 void setPush(int x) { 751 setFree(0); 752 points.insert(x); 753 } 754 755 void rotate(int balance) { 756 cbase = balance - cbase; 757 cdir = -cdir; 758 seg = {balance - seg.second, balance - seg.first}; 759 } 760 761 int tr(int x) { 762 return cbase + cdir*x; 763 } 764 765 int anti(int x) { 766 return cdir * (x - cbase); 767 } 768 769 bool in(int x) { 770 if (points.count(anti(x))) 771 return true; 772 return (seg.first <= x && x <= seg.second); 773 } 774 775 void push(int x) { 776 points.insert(anti(x)); 777 } 778 779 void popBelow(int x) { 780 seg.second = min(seg.second, x); 781 auto nextIt = [&] { 782 return (cdir == 1 ? prev(points.end()) : points.begin()); 783 }; 784 while (!points.empty() && tr(*nextIt()) > x) 785 points.erase(nextIt()); 786 } 787 788 bool empty() { 789 return points.empty() && seg.first > seg.second; 790 } 791 }; 792 793 void solve() { 794 int n; cin >> n; 795 EndSet util; 796 int curAns = 0; 797 for (int i = 0; i < n; ++i) { 798 int x; cin >> x; 799 util.popBelow(x-1); 800 if (x % 2 == 0 && util.in(x/2)) { 801 curAns += 2; 802 util.setPush(x/2); 803 } else if (util.empty()) { 804 if (x % 2 == 0) 805 curAns += 1, util.setPush(x/2); 806 else 807 util.setFree(x-1); 808 } else { 809 curAns += 1; 810 if (x % 2 == 0) 811 util.push(x/2); 812 } 813 util.rotate(x); 814 } 815 cout << 2*n - curAns << "\n"; 816 } 817 818 signed main() { 819 ios::sync_with_stdio(false), cin.tie(0); 820 int nbTests; 821 cin >> nbTests; 822 for (int iTest = 0; iTest < nbTests; ++iTest) { 823 solve(); 824 } 825 } 826 ``` 827 828 Div1F by [bthero](/profile/bthero "Master bthero") 829 830 **Editorial** 831 832 ... 833 834 **Code in C++ (BThero)** 835 836 ``` 837 // chrono::system_clock::now().time_since_epoch().count() 838 #include<bits/stdc++.h> 839 840 #define pb push_back 841 #define eb emplace_back 842 #define mp make_pair 843 #define fi first 844 #define se second 845 #define all(x) (x).begin(), (x).end() 846 #define debug(x) cerr << #x << " = " << x << endl; 847 848 using namespace std; 849 850 typedef long long ll; 851 typedef pair<int, int> pii; 852 typedef vector<int> vi; 853 typedef vector<vi> vvi; 854 855 const int dx[] = {0, 1, 0, -1}; 856 const int dy[] = {1, 0, -1, 0}; 857 const char dc[] = {'R', 'D', 'L', 'U'}; 858 const int INF = (int)1e6; 859 const int MAXN = (int)3e5 + 5; 860 861 namespace { 862 struct Edge { 863 int v, to, f, c; 864 865 Edge() { 866 v = to = f = c = 0; 867 } 868 869 Edge(int v, int to, int c) : v(v), to(to), c(c) { 870 f = 0; 871 } 872 }; 873 874 vector<Edge> e; 875 vector<int> adj[MAXN]; 876 int ptr[MAXN], d[MAXN], q[MAXN]; 877 int S, T, newS, newT, V; 878 int cap[2][MAXN]; 879 880 void prep() { 881 e.clear(); 882 883 for (int i = 0; i < V; ++i) { 884 adj[i].clear(); 885 ptr[i] = d[i] = q[i] = 0; 886 cap[0][i] = cap[1][i] = 0; 887 } 888 } 889 890 void addEdge(int u, int v, int c) { 891 //printf("E %d %d %d\n", u, v, c); 892 893 adj[u].pb((int)e.size()); 894 e.pb(Edge(u, v, c)); 895 adj[v].pb((int)e.size()); 896 e.pb(Edge(v, u, 0)); 897 } 898 899 void addEdgeLim(int u, int v) { 900 //printf("F %d %d\n", u, v); 901 ++cap[0][v]; 902 ++cap[1][u]; 903 } 904 905 bool bfs() { 906 fill(d, d + V, -1); 907 d[newS] = 0; 908 int l = 0, r = 0; 909 q[r++] = newS; 910 911 while (l < r) { 912 int v = q[l++]; 913 914 for (int id : adj[v]) { 915 if (e[id].f < e[id].c) { 916 int to = e[id].to; 917 918 if (d[to] == -1) { 919 d[to] = d[v] + 1; 920 q[r++] = to; 921 } 922 } 923 } 924 } 925 926 return d[newT] != -1; 927 } 928 929 int dfs(int v, int flow = INF) { 930 if (!flow || v == newT) { 931 return flow; 932 } 933 934 int sum = 0; 935 936 for (; ptr[v] < (int)adj[v].size(); ++ptr[v]) { 937 int id = adj[v][ptr[v]]; 938 int to = e[id].to; 939 int can = e[id].c - e[id].f; 940 941 if (d[to] != d[v] + 1 || can == 0) { 942 continue; 943 } 944 945 int pushed = dfs(to, min(flow, can)); 946 947 if (pushed > 0) { 948 e[id].f += pushed; 949 e[id ^ 1].f -= pushed; 950 sum += pushed; 951 flow -= pushed; 952 953 if (flow == 0) { 954 return sum; 955 } 956 } 957 } 958 959 return sum; 960 } 961 962 int maxFlow() { 963 int ret = 0; 964 965 while (bfs()) { 966 fill(ptr, ptr + V, 0); 967 968 while (int pushed = dfs(newS)) { 969 ret += pushed; 970 } 971 } 972 973 return ret; 974 } 975 } 976 977 vvi arr, follow; 978 int n, m; 979 980 bool inside(int x, int y) { 981 return 0 <= x && x < n && 0 <= y && y < m; 982 } 983 984 int id(int x, int y) { 985 return x * m + y; 986 } 987 988 void solve() { 989 scanf("%d %d", &n, &m); 990 arr = follow = vvi(n, vi(m, -1)); 991 S = n * m; 992 T = S + 1; 993 newS = T + 1; 994 newT = newS + 1; 995 V = newT + 1; 996 prep(); 997 998 for (int i = 0; i < n; ++i) { 999 for (int j = 0; j < m; ++j) { 1000 scanf("%d", &arr[i][j]); 1001 } 1002 } 1003 1004 for (int i = 0; i < n; ++i) { 1005 for (int j = 0; j < m; ++j) { 1006 for (int dir = 0; dir < 4; ++dir) { 1007 int ni = i + dx[dir], nj = j + dy[dir]; 1008 1009 if (inside(ni, nj)) { 1010 if (arr[ni][nj] < arr[i][j]) { 1011 follow[i][j] = dir; 1012 } 1013 else if ((i + j) % 2 == 0 && arr[ni][nj] == arr[i][j]) { 1014 addEdge(id(i, j), id(ni, nj), 1); 1015 } 1016 } 1017 } 1018 1019 if (follow[i][j] == -1) { 1020 // important vertex 1021 if ((i + j) % 2) { 1022 addEdgeLim(id(i, j), T); 1023 } 1024 else { 1025 addEdgeLim(S, id(i, j)); 1026 } 1027 } 1028 else { 1029 if ((i + j) % 2) { 1030 addEdge(id(i, j), T, 1); 1031 } 1032 else { 1033 addEdge(S, id(i, j), 1); 1034 } 1035 } 1036 } 1037 } 1038 1039 for (int i = 0; i <= T; ++i) { 1040 if (cap[0][i] > 0) { 1041 addEdge(newS, i, cap[0][i]); 1042 } 1043 1044 if (cap[1][i] > 0) { 1045 addEdge(i, newT, cap[1][i]); 1046 } 1047 } 1048 1049 addEdge(T, S, INF); 1050 maxFlow(); 1051 1052 for (int id : adj[newS]) { 1053 if (e[id].f != e[id].c) { 1054 printf("NO\n"); 1055 return; 1056 } 1057 } 1058 1059 vvi ansv, ansc; 1060 ansv = ansc = vvi(n, vi(m)); 1061 1062 for (int i = 0; i < n; ++i) { 1063 for (int j = 0; j < m; ++j) { 1064 int dir = follow[i][j]; 1065 1066 if (dir != -1) { 1067 int ni = i + dx[dir], nj = j + dy[dir]; 1068 ansv[i][j] = arr[i][j] - arr[ni][nj]; 1069 ansc[i][j] = dir; 1070 } 1071 } 1072 } 1073 1074 for (Edge it : e) { 1075 int v = it.v, to = it.to; 1076 1077 if (max(v, to) < n * m && it.f == it.c && it.c == 1) { 1078 int ax = v / m, ay = v % m; 1079 int bx = to / m, by = to % m; 1080 ansv[ax][ay] = arr[ax][ay] - 1; 1081 ansv[bx][by] = 1; 1082 1083 for (int dir = 0; dir < 4; ++dir) { 1084 if (mp(ax + dx[dir], ay + dy[dir]) == mp(bx, by)) { 1085 ansc[ax][ay] = dir; 1086 ansc[bx][by] = (dir + 2) % 4; 1087 } 1088 } 1089 } 1090 } 1091 1092 printf("YES\n"); 1093 1094 for (int i = 0; i < n; ++i) { 1095 for (int j = 0; j < m; ++j) { 1096 printf("%d%c", ansv[i][j], " \n"[j == m - 1]); 1097 } 1098 } 1099 1100 for (int i = 0; i < n; ++i) { 1101 for (int j = 0; j < m; ++j) { 1102 printf("%c%c", dc[ansc[i][j]], " \n"[j == m - 1]); 1103 } 1104 } 1105 } 1106 1107 int main() { 1108 int tt; 1109 scanf("%d", &tt); 1110 1111 while (tt--) { 1112 solve(); 1113 } 1114 1115 return 0; 1116 } 1117 ```