1030.md (18677B)
1 Source: https://codeforces.com/blog/entry/62013 2 3 [1030A - In Search of an Easy Problem](/contest/1030/problem/A "Technocup 2019 - Elimination Round 1") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution** 10 11 ``` 12 #include<bits/stdc++.h> 13 14 using namespace std; 15 16 int main() { 17 int n; cin >> n; 18 19 int curMax = 0; 20 for(int i = 0; i < n; i++) { 21 int curAns; cin >> curAns; 22 curMax = max(curMax, curAns); 23 } 24 puts(curMax > 0 ? "HARD" : "EASY"); 25 return 0; 26 } 27 ``` 28 29 [1030B - Vasya and Cornfield](/contest/1030/problem/B "Technocup 2019 - Elimination Round 1") 30 31 **Tutorial** 32 33 Tutorial is loading... 34 35 **Solution** 36 37 ``` 38 #include<bits/stdc++.h> 39 40 using namespace std; 41 42 int n, d; 43 int m; 44 45 int main() { 46 ios_base::sync_with_stdio(false); 47 cin.tie(NULL); 48 49 cin >> n >> d; 50 cin >> m; 51 for(int i = 0; i < m; ++i){ 52 int x, y; 53 cin >> x >> y; 54 55 bool ok = true; 56 if(!((x - y) <= d && (x - y) >= -d)) 57 ok = false; 58 if(!((x + y) <= n + n - d && (x + y) >= d)) 59 ok = false; 60 61 if(ok) puts("YES"); 62 else puts("NO"); 63 } 64 return 0; 65 } 66 ``` 67 68 [1030C - Vasya and Golden Ticket](/contest/1030/problem/C "Technocup 2019 - Elimination Round 1") 69 70 **Tutorial** 71 72 Tutorial is loading... 73 74 **Solution** 75 76 ``` 77 #include<bits/stdc++.h> 78 79 using namespace std; 80 81 int n; 82 string s; 83 84 int main() { 85 ios_base::sync_with_stdio(false); 86 cin.tie(NULL); 87 88 cin >> n >> s; 89 int sum = 0; 90 for(int i = 0; i < n - 1; ++i){ 91 sum += s[i] - '0'; 92 93 bool ok = true; 94 int pos = i + 1; 95 int sum2 = 0; 96 while(pos < n){ 97 sum2 = s[pos++] - '0'; 98 while(pos < n && sum2 + s[pos] - '0' <= sum){ 99 sum2 += s[pos] - '0'; 100 ++pos; 101 } 102 if(sum2 != sum) ok = false; 103 } 104 105 if(sum2 != sum) ok = false; 106 if(ok){ 107 puts("YES"); 108 return 0; 109 } 110 } 111 112 puts("NO"); 113 return 0; 114 } 115 ``` 116 117 [1030D - Vasya and Triangle](/contest/1030/problem/D "Technocup 2019 - Elimination Round 1") 118 119 **Tutorial** 120 121 Tutorial is loading... 122 123 **Solution** 124 125 ``` 126 #include<bits/stdc++.h> 127 128 using namespace std; 129 130 long long gcd(long long a, long long b){ 131 return a? gcd(b % a, a) : b; 132 } 133 134 int main() { 135 //freopen("input.txt", "r", stdin); 136 137 long long n, m, k; 138 cin >> n >> m >> k; 139 140 bool isEven = k % 2 == 0; 141 long long p = n * m; 142 if(isEven) k /= 2; 143 144 if(p % k != 0){ 145 cout << "NO" << endl; 146 return 0; 147 } 148 149 long long x = gcd(n, k); 150 k /= x; 151 long long a = n / x; 152 153 x = gcd(m, k); 154 k /= x; 155 assert(k == 1); 156 long long b = m / x; 157 158 159 if(!isEven){ 160 if(a < n) 161 a += a; 162 else{ 163 assert(b < m); 164 b += b; 165 } 166 } 167 168 cout << "YES" << endl; 169 cout << "0 0\n"; 170 cout << 0 << ' ' << b << endl; 171 cout << a << ' ' << 0 << endl; 172 173 return 0; 174 } 175 ``` 176 177 [1030E - Vasya and Good Sequences](/contest/1030/problem/E "Technocup 2019 - Elimination Round 1") 178 179 **Tutorial** 180 181 Tutorial is loading... 182 183 **Solution** 184 185 ``` 186 #include<bits/stdc++.h> 187 188 using namespace std; 189 190 const int N = int(3e5) + 9; 191 192 int n; 193 long long a[N]; 194 int b[N]; 195 int cnt[2][N]; 196 197 int main() { 198 ios_base::sync_with_stdio(false); 199 cin.tie(NULL); 200 201 cin >> n; 202 for(int i = 0; i <n; ++i){ 203 cin >> a[i]; 204 b[i] = __builtin_popcountll(a[i]); 205 } 206 207 long long res = 0; 208 int sufSum = 0; 209 cnt[0][n] = 1; 210 for(int i = n - 1; i >= 0; --i){ 211 int sum = 0, mx = 0; 212 int lstJ = i; 213 int add = 0; 214 for(int j = i; j < n && j - i < 65; ++j){ 215 sum += b[j]; 216 mx = max(mx, b[j]); 217 if(mx > sum - mx && sum % 2 == 0) --add; 218 lstJ = j; 219 } 220 221 sufSum += b[i]; 222 add += cnt[sufSum & 1][i + 1]; 223 res += add; 224 225 cnt[0][i] = cnt[0][i + 1]; 226 cnt[1][i] = cnt[1][i + 1]; 227 if(sufSum & 1) ++cnt[1][i]; 228 else ++cnt[0][i]; 229 } 230 231 cout << res << endl; 232 return 0; 233 } 234 ``` 235 236 [1030F - Putting Boxes Together](/contest/1030/problem/F "Technocup 2019 - Elimination Round 1") 237 238 **Tutorial** 239 240 Tutorial is loading... 241 242 **Fenwick Solution** 243 244 ``` 245 #include<bits/stdc++.h> 246 247 using namespace std; 248 249 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 250 typedef long long li; 251 252 const int MOD = int(1e9) + 7; 253 254 int norm(int a) { 255 if(a >= MOD) 256 a -= MOD; 257 if(a < 0) 258 a += MOD; 259 return a; 260 } 261 262 int norm(const li &a) { 263 return norm(int(a % MOD)); 264 } 265 266 int mul(int a, int b) { 267 return int((a * 1ll * b) % MOD); 268 } 269 270 const int N = 200 * 1000 + 555; 271 272 int n, q; 273 int a[N], w[N]; 274 275 inline bool read() { 276 if(!(cin >> n >> q)) 277 return false; 278 fore(i, 0, n) 279 assert(scanf("%d", &a[i]) == 1); 280 fore(i, 0, n) 281 assert(scanf("%d", &w[i]) == 1); 282 return true; 283 } 284 285 li fW[N], fAW[N]; 286 287 void inc(li f[N], int pos, li val) { 288 for(; pos < N; pos |= pos + 1) 289 f[pos] += val; 290 } 291 292 li sum(li f[N], int pos) { 293 li ans = 0; 294 for(; pos >= 0; pos = (pos & (pos + 1)) - 1) 295 ans += f[pos]; 296 return ans; 297 } 298 299 li getSum(li f[N], int l, int r) { 300 return sum(f, r - 1) - sum(f, l - 1); 301 } 302 303 int getNSum(li f[N], int l, int r) { 304 return norm(sum(f, r - 1) - sum(f, l - 1)); 305 } 306 307 inline void solve() { 308 fore(i, 0, n) { 309 a[i] -= i; 310 inc(fW, i, w[i]); 311 inc(fAW, i, mul(a[i], w[i])); 312 } 313 314 fore(_, 0, q) { 315 int x, y; 316 assert(scanf("%d%d", &x, &y) == 2); 317 if(x < 0) { 318 x = -x - 1; 319 inc(fW, x, -w[x]); 320 inc(fAW, x, -mul(a[x], w[x])); 321 322 w[x] = y; 323 inc(fW, x, w[x]); 324 inc(fAW, x, mul(a[x], w[x])); 325 } else { 326 x--; 327 li sum = getSum(fW, x, y); 328 329 int lf = x, rg = y; 330 while(rg - lf > 1) { 331 int mid = (lf + rg) >> 1; 332 if(2 * getSum(fW, x, mid) > sum) 333 rg = mid; 334 else 335 lf = mid; 336 } 337 assert(x <= lf && lf < y); 338 339 int ans = norm(mul(a[lf], getNSum(fW, x, lf)) - getNSum(fAW, x, lf)); 340 ans = norm(ans + norm(getNSum(fAW, lf, y) - mul(a[lf], getNSum(fW, lf, y))) ); 341 printf("%d\n", ans); 342 } 343 } 344 } 345 346 int main() { 347 #ifdef _DEBUG 348 freopen("input.txt", "r", stdin); 349 int tt = clock(); 350 #endif 351 cout << fixed << setprecision(15); 352 353 if(read()) { 354 solve(); 355 356 #ifdef _DEBUG 357 cerr << "TIME = " << clock() - tt << endl; 358 tt = clock(); 359 #endif 360 } 361 return 0; 362 } 363 ``` 364 365 **Segment Tree Solution** 366 367 ``` 368 #include<bits/stdc++.h> 369 370 using namespace std; 371 372 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 373 #define sz(a) int((a).size()) 374 375 #define x first 376 #define y second 377 378 typedef long long li; 379 380 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 381 return out << "(" << p.x << ", " << p.y << ")"; 382 } 383 384 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 385 out << "["; 386 fore(i, 1, int(v.size())) { 387 if(i) out << ", "; 388 out << v[i]; 389 } 390 return out << "]"; 391 } 392 393 const int INF = int(1e9); 394 const li INF64 = li(1e18); 395 396 const int MOD = int(1e9) + 7; 397 398 int norm(int a) { 399 while(a >= MOD) 400 a -= MOD; 401 while(a < 0) 402 a += MOD; 403 return a; 404 } 405 406 int norm(const li &a) { 407 return norm(int(a % MOD)); 408 } 409 410 int mul(int a, int b) { 411 return int((a * 1ll * b) % MOD); 412 } 413 414 const int N = 300 * 1000 + 555; 415 416 int n, q; 417 int a[N], w[N]; 418 419 inline bool read() { 420 if(!(cin >> n >> q)) 421 return false; 422 fore(i, 0, n) 423 assert(scanf("%d", &a[i]) == 1); 424 fore(i, 0, n) 425 assert(scanf("%d", &w[i]) == 1); 426 return true; 427 } 428 429 li TW[4 * N], TAW[4 * N]; 430 431 void addVAl(li T[4 * N], int v, int l, int r, int pos, int val) { 432 if(l + 1 == r) { 433 assert(l == pos); 434 T[v] += val; 435 return; 436 } 437 int mid = (l + r) >> 1; 438 if(pos < mid) 439 addVAl(T, 2 * v + 1, l, mid, pos, val); 440 else 441 addVAl(T, 2 * v + 2, mid, r, pos, val); 442 T[v] = T[2 * v + 1] + T[2 * v + 2]; 443 } 444 445 li getSum(li T[4 * N], int v, int l, int r, int lf, int rg) { 446 if(l == lf && r == rg) 447 return T[v]; 448 int mid = (l + r) >> 1; 449 li ans = 0; 450 if(lf < mid) 451 ans += getSum(T, 2 * v + 1, l, mid, lf, min(mid, rg)); 452 if(rg > mid) 453 ans += getSum(T, 2 * v + 2, mid, r, max(lf, mid), rg); 454 return ans; 455 } 456 457 int getNSum(li T[4 * N], int l, int r) { 458 if(l >= r) return 0; 459 return int(getSum(T, 0, 0, n, l, r) % MOD); 460 } 461 462 pair<int, li> getPos(int v, int l, int r, int lf, int rg, li val) { 463 if(l == lf && r == rg) { 464 if(TW[v] <= val) 465 return make_pair(INF, TW[v]); 466 if(l + 1 == r) 467 return make_pair(l, 0); 468 } 469 int mid = (l + r) >> 1; 470 471 int res = INF; 472 li sum = 0; 473 if(lf < mid) { 474 auto cur = getPos(2 * v + 1, l, mid, lf, min(mid, rg), val); 475 res = min(res, cur.x); 476 sum += cur.y; 477 } 478 if(rg > mid && res == INF) { 479 auto cur = getPos(2 * v + 2, mid, r, max(lf, mid), rg, val - sum); 480 res = min(res, cur.x); 481 sum += cur.y; 482 } 483 return make_pair(res, sum); 484 } 485 486 inline void solve() { 487 fore(i, 0, n) { 488 a[i] -= i; 489 addVAl(TW, 0, 0, n, i, w[i]); 490 addVAl(TAW, 0, 0, n, i, mul(a[i], w[i])); 491 } 492 493 fore(_, 0, q) { 494 int x, y; 495 assert(scanf("%d%d", &x, &y) == 2); 496 if(x < 0) { 497 x = -x - 1; 498 addVAl(TW, 0, 0, n, x, -w[x]); 499 addVAl(TAW, 0, 0, n, x, -mul(a[x], w[x])); 500 501 w[x] = y; 502 addVAl(TW, 0, 0, n, x, w[x]); 503 addVAl(TAW, 0, 0, n, x, mul(a[x], w[x])); 504 } else { 505 x--; 506 li sum = getSum(TW, 0, 0, n, x, y); 507 int pos = getPos(0, 0, n, x, y, sum / 2).x; 508 assert(x <= pos && pos < y); 509 510 int ans = norm(mul(a[pos], getNSum(TW, x, pos)) - getNSum(TAW, x, pos)); 511 ans = norm(ans + norm(getNSum(TAW, pos, y) - mul(a[pos], getNSum(TW, pos, y))) ); 512 printf("%d\n", ans); 513 } 514 } 515 } 516 517 int main() { 518 #ifdef _DEBUG 519 freopen("input.txt", "r", stdin); 520 int tt = clock(); 521 #endif 522 cout << fixed << setprecision(15); 523 524 if(read()) { 525 solve(); 526 527 #ifdef _DEBUG 528 cerr << "TIME = " << clock() - tt << endl; 529 tt = clock(); 530 #endif 531 } 532 return 0; 533 } 534 ``` 535 536 [1030G - Linear Congruential Generator](/contest/1030/problem/G "Technocup 2019 - Elimination Round 1") 537 538 **Tutorial** 539 540 Tutorial is loading... 541 542 **Dynamic Connectivity Solution** 543 544 ``` 545 #include<bits/stdc++.h> 546 547 using namespace std; 548 549 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 550 #define sz(a) int((a).size()) 551 552 #define x first 553 #define y second 554 555 typedef long long li; 556 typedef pair<int, int> pt; 557 558 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 559 return out << "(" << p.x << ", " << p.y << ")"; 560 } 561 562 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 563 out << "["; 564 fore(i, 0, sz(v)) { 565 if(i) out << ", "; 566 out << v[i]; 567 } 568 return out << "]"; 569 } 570 571 const int MOD = int(1e9) + 7; 572 573 int mul(int a, int b) { 574 return int(a * 1ll * b % MOD); 575 } 576 577 int binPow(int a, int k) { 578 int ans = 1; 579 while(k > 0) { 580 if(k & 1) ans = mul(ans, a); 581 a = mul(a, a); 582 k >>= 1; 583 } 584 return ans; 585 } 586 587 const int M = 2000 * 1000 + 555; 588 const int N = 200 * 1000 + 555; 589 590 int n, p[N]; 591 592 inline bool read() { 593 if(!(cin >> n)) 594 return false; 595 fore(i, 0, n) 596 assert(scanf("%d", &p[i]) == 1); 597 return true; 598 } 599 600 int minD[M]; 601 vector<pt> ps[M]; 602 603 void precalc() { 604 iota(minD, minD + M, 0); 605 fore(i, 2, M) { 606 if(minD[i] < i) 607 continue; 608 609 for(li j = i * 1ll * i; j < M; j += i) 610 minD[j] = min(minD[j], i); 611 } 612 613 fore(i, 2, M) { 614 int v = i; 615 ps[i].clear(); 616 617 while(v > 1) { 618 int md = minD[v]; 619 if(ps[i].empty() || ps[i].back().x != md) 620 ps[i].emplace_back(md, 0); 621 ps[i].back().y++; 622 v /= md; 623 } 624 } 625 } 626 627 int baseA[M], cntNotZero = 0; 628 629 int a[M]; 630 int mark[M]; 631 632 void insert(int v) { 633 if(a[v] < 1) { 634 a[v] = 1; 635 mark[v] = 1; 636 return; 637 } 638 for(auto p : ps[v - 1]) { 639 a[p.x] = max(a[p.x], p.y); 640 if(mark[p.x]) { 641 mark[p.x] = 0; 642 insert(p.x); 643 } 644 } 645 } 646 647 vector<int*> pnt; 648 vector<int> val; 649 650 void upd(int &pos, int nval) { 651 pnt.push_back(&pos); 652 val.push_back(pos); 653 654 pos = nval; 655 } 656 657 void roll_back() { 658 *(pnt.back()) = val.back(); 659 pnt.pop_back(); 660 val.pop_back(); 661 } 662 663 bool ok[N]; 664 int cntSame = 0; 665 vector<int> Top[4 * N]; 666 667 void addOp(int v, int l, int r, int lf, int rg, int val) { 668 if(l == lf && r == rg) { 669 Top[v].push_back(val); 670 return; 671 } 672 int mid = (l + r) >> 1; 673 if(lf < mid) 674 addOp(2 * v + 1, l, mid, lf, min(mid, rg), val); 675 if(rg > mid) 676 addOp(2 * v + 2, mid, r, max(lf, mid), rg, val); 677 } 678 679 void insertDC(int v) { 680 if(a[v] < 1) { 681 upd(a[v], 1); 682 upd(mark[v], 1); 683 if(a[v] == baseA[v]) 684 upd(cntSame, cntSame + 1); 685 return; 686 } 687 for(auto p : ps[v - 1]) { 688 if(a[p.x] < p.y) { 689 upd(a[p.x], p.y); 690 if(a[p.x] == baseA[p.x]) 691 upd(cntSame, cntSame + 1); 692 } 693 if(mark[p.x]) { 694 upd(mark[p.x], 0); 695 insertDC(p.x); 696 } 697 } 698 } 699 700 void calcAns(int v, int l, int r) { 701 int curOp = sz(pnt); 702 for(int cv : Top[v]) 703 insertDC(cv); 704 705 if(l + 1 == r) { 706 ok[l] = cntSame == cntNotZero; 707 } else { 708 int mid = (l + r) >> 1; 709 calcAns(2 * v + 1, l, mid); 710 calcAns(2 * v + 2, mid, r); 711 } 712 while(sz(pnt) > curOp) 713 roll_back(); 714 } 715 716 inline void solve() { 717 memset(baseA, 0, sizeof baseA); 718 memset(a, 0, sizeof a); 719 memset(mark, 0, sizeof mark); 720 721 fore(i, 0, n) 722 insert(p[i]); 723 724 cntNotZero = 0; 725 fore(i, 0, M) { 726 baseA[i] = a[i]; 727 cntNotZero += a[i] > 0; 728 } 729 730 memset(a, 0, sizeof a); 731 memset(mark, 0, sizeof mark); 732 fore(i, 0, n) { 733 if(i > 0) 734 addOp(0, 0, n, 0, i, p[i]); 735 if(i + 1 < n) 736 addOp(0, 0, n, i + 1, n, p[i]); 737 } 738 calcAns(0, 0, n); 739 740 int lcm = 1; 741 fore(i, 1, M) 742 lcm = mul(lcm, binPow(i, baseA[i])); 743 int add = 0; 744 fore(i, 0, n) 745 if(ok[i]) 746 add = 1; 747 cout << (lcm + add) % MOD << endl; 748 } 749 750 int main() { 751 #ifdef _DEBUG 752 freopen("input.txt", "r", stdin); 753 int tt = clock(); 754 #endif 755 cout << fixed << setprecision(15); 756 757 precalc(); 758 if(read()) { 759 solve(); 760 761 #ifdef _DEBUG 762 cerr << "TIME = " << clock() - tt << endl; 763 tt = clock(); 764 #endif 765 } 766 return 0; 767 } 768 ``` 769 770 **Greedy Solution** 771 772 ``` 773 #include<bits/stdc++.h> 774 775 using namespace std; 776 777 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 778 #define sz(a) int((a).size()) 779 780 #define x first 781 #define y second 782 783 typedef long long li; 784 typedef pair<int, int> pt; 785 786 const int MOD = int(1e9) + 7; 787 788 int mul(int a, int b) { 789 return int(a * 1ll * b % MOD); 790 } 791 792 int binPow(int a, int k) { 793 int ans = 1; 794 while(k > 0) { 795 if(k & 1) ans = mul(ans, a); 796 a = mul(a, a); 797 k >>= 1; 798 } 799 return ans; 800 } 801 802 const int M = 2000 * 1000 + 555; 803 804 int minD[M]; 805 vector<pt> ps[M]; 806 807 inline void precalc() { 808 iota(minD, minD + M, 0); 809 810 fore(val, 2, M) { 811 if(minD[val] < val) 812 continue; 813 814 for(li j = val * 1ll * val; j < M; j += val) 815 minD[j] = min(minD[j], val); 816 } 817 818 fore(i, 2, M) { 819 int v = i; 820 ps[i].clear(); 821 822 while(v > 1) { 823 int md = minD[v]; 824 if(ps[i].empty() || ps[i].back().x != md) 825 ps[i].emplace_back(md, 0); 826 ps[i].back().y++; 827 v /= md; 828 } 829 } 830 } 831 832 int n; 833 vector<int> p; 834 835 inline bool read() { 836 if(!(cin >> n)) 837 return false; 838 p.assign(n, 0); 839 fore(i, 0, n) 840 assert(scanf("%d", &p[i]) == 1); 841 return true; 842 } 843 844 int a[M], cnt[M]; 845 846 inline void solve() { 847 sort(p.begin(), p.end(), greater<int>()); 848 849 for(int& cp : p) { 850 if(a[cp] == 0) { 851 a[cp] = 1; 852 cnt[cp] = 1; 853 } else { 854 cp--; 855 for(auto np : ps[cp]) { 856 if(a[np.x] < np.y) { 857 a[np.x] = np.y; 858 cnt[np.x] = 1; 859 } else if(a[np.x] == np.y) 860 cnt[np.x]++; 861 } 862 } 863 } 864 865 int add = 0; 866 for(int cp : p) { 867 bool un = false; 868 for(auto np : ps[cp]) 869 un |= (a[np.x] == np.y && cnt[np.x] == 1); 870 if(!un) 871 add = 1; 872 } 873 874 int lcm = 1; 875 fore(i, 2, M) 876 lcm = mul(lcm, binPow(i, a[i])); 877 cout << (lcm + add) % MOD << endl; 878 } 879 880 int main(){ 881 #ifdef _DEBUG 882 freopen("input.txt", "r", stdin); 883 int t = clock(); 884 #endif 885 cout << fixed << setprecision(10); 886 887 precalc(); 888 if(read()) { 889 solve(); 890 891 #ifdef _DEBUG 892 cerr << "TIME = " << clock() - t << endl; 893 #endif 894 } 895 return 0; 896 } 897 ``` 898 899 [1053E - Euler tour](/contest/1053/problem/E "Codeforces Round 512 (Div. 1, based on Technocup 2019 Elimination Round 1)") 900 901 **Tutorial** 902 903 Tutorial is loading... 904 905 **Solution** 906 907 ``` 908 #include <bits/stdc++.h> 909 910 using namespace std; 911 912 #define st first 913 #define nd second 914 #define PII pair <int, int> 915 916 const int N = 1e6 + 7; 917 918 int n; 919 int in[N]; 920 int ans[N]; 921 bool used[N]; 922 vector <int> unused; 923 924 int cnt; 925 deque <PII> cur; 926 vector <PII> getEqual; 927 928 set <int> S; 929 vector <int> place[N]; 930 vector <pair <int, int> > order; 931 932 bool check(){ 933 if(in[1] != 0 && in[n + n - 1] != 0 && in[1] != in[n + n - 1]) 934 return false; 935 936 for(int i = 1; i + 1 < n + n; ++i) 937 if(in[i] == in[i + 1] && in[i] != 0) 938 return false; 939 940 for(int i = 1; i < n + n; ++i){ 941 if(in[i] == 0) 942 continue; 943 944 if(place[in[i]].size() == 0) 945 order.push_back({i, in[i]}); 946 place[in[i]].push_back(i); 947 } 948 949 for(int i = 1; i <= n; ++i) 950 for(int j = 1; j < place[i].size(); ++j) 951 if(place[i][j]%2 != place[i][j - 1]%2) 952 return false; 953 954 S.insert(n + n); 955 sort(order.begin(), order.end()); 956 957 for(auto v: order){ 958 auto it = S.lower_bound(v.first); 959 if(*it < place[v.second].back()) 960 return false; 961 962 for(int c: place[v.second]) 963 S.insert(c); 964 } 965 966 return true; 967 } 968 969 inline int get(){ 970 if(unused.size() == 0){ 971 puts("no"); 972 exit(0); 973 } 974 975 int ret = unused.back(); 976 unused.pop_back(); 977 return ret; 978 } 979 980 void go(){ 981 deque <PII> help; 982 while(help.size() + cur.size() >= 3){ 983 if(help.size() < 3){ 984 help.push_back(cur.front()); 985 cur.pop_front(); 986 continue; 987 } 988 989 PII v1 = help.back(); help.pop_back(); 990 PII v2 = help.back(); help.pop_back(); 991 PII v3 = help.back(); help.pop_back(); 992 993 if(v1.st == 0 && v2.st != 0 && v3.st != 0){ 994 ans[v1.nd] = v3.st; 995 help.push_back(v3); 996 } 997 else{ 998 help.push_back(v3); 999 help.push_back(v2); 1000 help.push_back(v1); 1001 } 1002 1003 if(cur.size() == 0) 1004 break; 1005 1006 help.push_back(cur.front()); 1007 cur.pop_front(); 1008 } 1009 1010 while(help.size()){ 1011 cur.push_back(help.front()); 1012 help.pop_front(); 1013 } 1014 } 1015 1016 void solve(int root){ 1017 int need = (cur.size() + 1) / 2 - cnt; 1018 if(need < 0){ 1019 puts("no"); 1020 exit(0); 1021 } 1022 deque <PII> help; 1023 1024 while(cur.size()){ 1025 auto v = cur.front(); 1026 cur.pop_front(); 1027 1028 if(need > 0 && v.st == 0){ 1029 --need; 1030 v.st = get(); 1031 ans[v.nd] = v.st; 1032 } 1033 1034 help.push_back(v); 1035 } 1036 1037 while(help.size()){ 1038 cur.push_front(help.front()); 1039 help.pop_front(); 1040 } 1041 1042 go(); 1043 if(root == -1 && cur.back().st == 0){ 1044 root = cur.front().st; 1045 ans[cur.back().nd] = root; 1046 1047 cur.pop_front(); 1048 cur.pop_back(); 1049 solve(root); 1050 return; 1051 } 1052 1053 reverse(cur.begin(), cur.end()); 1054 go(); 1055 1056 while(cur.size() > 0){ 1057 auto v = cur.front(); 1058 cur.pop_front(); 1059 1060 if(v.st == 0) 1061 ans[v.nd] = root; 1062 } 1063 1064 } 1065 1066 int main(){ 1067 scanf("%d", &n); 1068 for(int i = 1; i < n + n; ++i){ 1069 scanf("%d", &in[i]); 1070 used[in[i]] = true; 1071 } 1072 1073 if(!check()){ 1074 puts("no"); 1075 return 0; 1076 } 1077 1078 if(in[1] != 0) 1079 in[n + n - 1] = in[1]; 1080 else if(in[n + n - 1] != 0) 1081 in[1] = in[n + n - 1]; 1082 1083 for(int i = 1; i <= n; ++i){ 1084 if(!used[i]) 1085 unused.push_back(i); 1086 used[i] = false; 1087 } 1088 1089 for(int i = 1; i < n + n; ++i) 1090 ans[i] = in[i]; 1091 1092 for(int i = 1; i < n + n; ++i){ 1093 if(in[i] == 0){ 1094 getEqual.push_back({in[i], i}); 1095 continue; 1096 } 1097 1098 if(used[in[i]]){ 1099 cnt = 0; 1100 while(getEqual.back().st != in[i]){ 1101 if(getEqual.back().st > 0){ 1102 ++cnt; 1103 used[getEqual.back().st] = false; 1104 } 1105 1106 cur.push_front(getEqual.back()); 1107 getEqual.pop_back(); 1108 } 1109 1110 solve(in[i]); 1111 continue; 1112 } 1113 1114 getEqual.push_back({in[i], i}); 1115 used[in[i]] = true; 1116 } 1117 1118 cnt = 0; 1119 while(getEqual.size()){ 1120 if(getEqual.back().st > 0){ 1121 ++cnt; 1122 used[getEqual.back().st] = false; 1123 } 1124 1125 cur.push_front(getEqual.back()); 1126 getEqual.pop_back(); 1127 } 1128 1129 solve(-1); 1130 puts("yes"); 1131 for(int i = 1; i < n + n; ++i) 1132 printf("%d%c", ans[i], i == n + n - 1 ? '\n' : ' '); 1133 return 0; 1134 } 1135 ```