1329.md (20532B)
1 Source: https://codeforces.com/blog/entry/75559 2 3 Tutorial is loading... 4 5 **author's code:** 6 7 ``` 8 #include<cstdio> 9 const int MAX_V = 201; 10 bool achieve[MAX_V]; 11 void solve() { 12 int n, x; 13 scanf("%d%d", &n, &x); 14 for(int i = 1; i <= n + x; i++) { 15 achieve[i] = false; 16 } 17 for(int i = 1; i <= n; i++) { 18 int ranking; 19 scanf("%d", &ranking); 20 achieve[ranking] = true; 21 } 22 for(int k = n + x; k > 0; k--) { 23 int v = 0; 24 for(int i = 1; i <= k; i++) { 25 if(!achieve[i]) v++; 26 } 27 if(v <= x) { 28 printf("%d\n", k); 29 return; 30 } 31 } 32 } 33 int main() { 34 int T; 35 scanf("%d", &T); 36 while(T--) solve(); 37 return 0; 38 } 39 ``` 40 41 Tutorial is loading... 42 43 **author's code** 44 45 ``` 46 #include<cstdio> 47 const int SIZE = 200000; 48 int p[SIZE]; 49 int ans[SIZE][2]; 50 int ans_cnt; 51 bool judge(int a[], int n){ 52 static int used[SIZE+1]; 53 for(int i = 1; i <= n; i++) used[i] = 0; 54 for(int i = 0; i < n; i++) used[a[i]] = 1; 55 for(int i = 1; i <= n; i++) { 56 if(!used[i]) return 0; 57 } 58 return 1; 59 } 60 bool judge(int len1, int n){ 61 return judge(p, len1) && judge(p + len1, n - len1); 62 } 63 int main() { 64 int t = 0; 65 scanf("%d", &t); 66 while(t--) { 67 ans_cnt = 0; 68 int n; 69 scanf("%d", &n); 70 int ma=0; 71 for(int i = 0; i < n; i++) { 72 scanf("%d", &p[i]); 73 if(ma < p[i]) ma = p[i]; 74 } 75 if(judge(n - ma,n)) { 76 ans[ans_cnt][0] = n - ma; 77 ans[ans_cnt++][1] = ma; 78 } 79 if(ma * 2 != n && judge(ma,n)) { 80 ans[ans_cnt][0] = ma; 81 ans[ans_cnt++][1] = n - ma; 82 } 83 printf("%d\n", ans_cnt); 84 for(int i = 0; i < ans_cnt; i++) { 85 printf("%d %d\n", ans[i][0], ans[i][1]); 86 } 87 } 88 return 0; 89 } 90 ``` 91 92 Tutorial is loading... 93 94 **author's code** 95 96 ``` 97 #include<bits/stdc++.h> 98 const int SIZE = 100002; 99 int len[SIZE]; 100 long long suffix_sum[SIZE]; 101 void err() {puts("-1");} 102 void solve() { 103 int N, M; 104 scanf("%d%d", &N, &M); 105 for(int i = 1; i <= M; i++) { 106 scanf("%d", &len[i]); 107 if(len[i] + i - 1 > N) { 108 err(); 109 return; 110 } 111 } 112 for(int i = M; i > 0; i--) { 113 suffix_sum[i] = suffix_sum[i + 1] + len[i]; 114 } 115 if(suffix_sum[1] < N) { 116 err(); 117 return; 118 } 119 for(int i = 1; i <= M; i++) { 120 printf("%lld", std::max((long long)i, N - suffix_sum[i] + 1)); 121 if(i < M) putchar(' '); 122 else puts(""); 123 } 124 } 125 int main() { 126 solve(); 127 return 0; 128 } 129 ``` 130 131 Tutorial is loading... 132 133 **UPD: [onthefloor](/profile/onthefloor "Мастер onthefloor") provides proof for what I mention** [here](https://codeforces.com/blog/entry/75559?#comment-597742). 134 135 **author's code** 136 137 ``` 138 #include<bits/stdc++.h> 139 void solve(){ 140 int d, m; 141 scanf("%d%d",&d, &m); 142 long long answer=1; 143 for(int i = 0; i < 30; i++) { 144 if(d < (1 << i)) break; 145 answer = answer * (std::min((1 << (i+1)) - 1, d) - (1 << i) + 2) % m; 146 } 147 answer--; 148 if(answer < 0) answer += m; 149 printf("%lld\n",answer); 150 } 151 int main() { 152 int T; 153 scanf("%d", &T); 154 while(T--) { 155 solve(); 156 } 157 } 158 ``` 159 160 Tutorial is loading... 161 162 [a super simple solution which is differet to this blog](https://codeforces.com/blog/entry/75559?#comment-597934) provided by [Swistakk](/profile/Swistakk "Легендарный гроссмейстер Swistakk"). 163 164 **author's code (from bottom to top with min heap)** 165 166 ``` 167 #include<bits/stdc++.h> 168 using namespace std; 169 const int SIZE = 1<<20; 170 int INF = 1000000001; 171 pair<int, int> a[SIZE]; 172 int final_v[SIZE]; 173 bool used[SIZE]; 174 int h, g; 175 void pull(int id) { 176 while(a[id] > min(a[id<<1], a[(id<<1)|1])) { 177 if(a[id<<1] < a[(id << 1) | 1]) { 178 swap(a[id<<1], a[id]); 179 id <<= 1; 180 } 181 else { 182 swap(a[(id<<1)|1], a[id]); 183 id = (id << 1) | 1; 184 } 185 if(id >= (1 << h)) return; 186 } 187 } 188 void solve() { 189 scanf("%d%d", &h, &g); 190 long long an = 0; 191 for(int i = 1; i < (1 << h); i++) { 192 used[i] = 0; 193 scanf("%d", &a[i].first); 194 a[i].second = i; 195 final_v[i] = 0; 196 } 197 h--; 198 for(int lv = h - 1; lv >= 0; lv--) { 199 int ll = 1 << lv; 200 int rr = 1 << (lv + 1); 201 for(int i = ll; i < rr; i++) { 202 pair<int, int> tmp = a[i]; 203 int bot = i << (h - lv); 204 a[i] = a[bot]; 205 a[bot] = make_pair(INF, 0); 206 pull(i); 207 if(lv < g) { 208 int need_mi = max(final_v[i * 2], final_v[i * 2 + 1]); 209 while(a[i].first < need_mi) { 210 a[i] = make_pair(INF, 0); 211 pull(i); 212 } 213 an += final_v[i] = a[i].first; 214 used[a[i].second] = 1; 215 a[i] = tmp; 216 pull(i); 217 } 218 else { 219 a[bot] = tmp; 220 } 221 } 222 } 223 printf("%lld\n", an); 224 bool first_time = true; 225 for(int i = (1 << (h + 1)) - 1; i > 0; i--) { 226 if(!used[i]) { 227 if(!first_time) printf(" "); 228 else first_time = false; 229 printf("%d", i); 230 } 231 } 232 puts(""); 233 } 234 int main(){ 235 int T; 236 scanf("%d", &T); 237 while(T--) solve(); 238 return 0; 239 } 240 ``` 241 242 **isaf27's code(from bottom to top with sorted array)** 243 244 ``` 245 //#pragma GCC optimize("O3") 246 #include <bits/stdc++.h> 247 248 using namespace std; 249 250 //defines 251 typedef long long ll; 252 typedef long double ld; 253 #define TIME clock() * 1.0 / CLOCKS_PER_SEC 254 #define prev _prev 255 #define y0 _y0 256 #define kill _kill 257 258 //permanent constants 259 const ld pi = acos(-1.0); 260 const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; 261 const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; 262 const int dx[4] = {0, 1, 0, -1}; 263 const int dy[4] = {1, 0, -1, 0}; 264 const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0}; 265 const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1}; 266 const int alf = 26; 267 const int dig = 10; 268 const int two = 2; 269 const int th = 3; 270 const ll prost = 239; 271 const ll btc = 30; 272 const ld eps = 1e-8; 273 const ll INF = (ll)(1e18 + 239); 274 const int BIG = (int)(1e9 + 239); 275 const int MOD = 1e9 + 7; // 276 277 //random 278 mt19937 rnd(239); //(chrono::high_resolution_clock::now().time_since_epoch().count()); 279 280 //constants 281 const int M = (int)(2e5 + 239); 282 const int N = (int)(2e3 + 239); 283 const int L = 20; 284 const int T = (1 << 20) + 239; 285 const int B = 500; 286 const int X = 35; 287 const int T2 = 2 * T; 288 289 int h, g, a[T2], n; 290 bool mark[T]; 291 int id[T], buf[T], timer; 292 293 bool cmp(int i, int j) 294 { 295 return (a[i] < a[j]); 296 } 297 298 int pos; 299 300 void dfs_write(int p) 301 { 302 id[pos++] = p; 303 if (2 * p + 1 <= n) 304 { 305 dfs_write(2 * p); 306 dfs_write(2 * p + 1); 307 } 308 } 309 310 int dfs(int p, int sz) 311 { 312 if ((1 << (g - 1)) <= p && p < (1 << g)) 313 { 314 int l = timer; 315 timer += sz; 316 pos = l; 317 dfs_write(p); 318 sort(id + l, id + l + sz, cmp); 319 mark[id[l]] = true; 320 return id[l]; 321 } 322 int l = timer; 323 int new_sz = ((sz - 1) / 2); 324 int s1 = dfs(2 * p, new_sz); 325 int s2 = dfs(2 * p + 1, new_sz); 326 merge(id + l, id + l + new_sz, id + l + new_sz, id + l + new_sz + new_sz, buf, cmp); 327 buf[sz - 1] = p; 328 for (int i = 0; i < sz; i++) 329 id[i + l] = buf[i]; 330 timer++; 331 if (cmp(s1, s2)) 332 s1 = s2; 333 for (int i = 0; i < sz; i++) 334 if (cmp(s1, id[i + l])) 335 { 336 mark[id[i + l]] = true; 337 return id[i + l]; 338 } 339 return 0; 340 } 341 342 void rm(int i) 343 { 344 if (a[2 * i] == 0 && a[2 * i + 1] == 0) 345 { 346 a[i] = 0; 347 mark[i] = false; 348 return; 349 } 350 if (a[2 * i] > a[2 * i + 1]) 351 { 352 a[i] = a[2 * i]; 353 mark[i] = mark[2 * i]; 354 rm(2 * i); 355 } 356 else 357 { 358 a[i] = a[2 * i + 1]; 359 mark[i] = mark[2 * i + 1]; 360 rm(2 * i + 1); 361 } 362 } 363 364 void dfs_ans(int p) 365 { 366 while (a[p] != 0 && !mark[p]) 367 { 368 cout << p << " "; 369 rm(p); 370 } 371 if (a[p] == 0) 372 return; 373 dfs_ans(2 * p); 374 dfs_ans(2 * p + 1); 375 } 376 377 void solve() 378 { 379 cin >> h >> g; 380 n = (1 << h) - 1; 381 for (int i = 1; i <= n; i++) 382 cin >> a[i]; 383 for (int i = 1; i <= n; i++) 384 mark[i] = false; 385 timer = 0; 386 dfs(1, n); 387 ll ans = 0; 388 for (int i = 1; i <= n; i++) 389 if (mark[i]) 390 ans += a[i]; 391 cout << ans << "\n"; 392 dfs_ans(1); 393 cout << "\n"; 394 for (int i = 0; i <= n; i++) 395 a[i] = 0; 396 } 397 398 int32_t main() 399 { 400 #ifdef ONPC 401 freopen("input", "r", stdin); 402 #endif 403 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 404 int t; 405 cin >> t; 406 while (t--) 407 solve(); 408 return 0; 409 } 410 ``` 411 412 **author's code (from top to bottom)** 413 414 ``` 415 #include<bits/stdc++.h> 416 using namespace std; 417 const int SIZE = 1<<20; 418 int INF = 1000000001; 419 int a[SIZE], ops[SIZE]; 420 int h, g; 421 int qq[24], qn; 422 int pull(int id) { 423 int tmp = a[id]; 424 a[id] = 0; 425 qn = 0; 426 qq[qn++] = id; 427 while(id * 2 < (1 << h) && a[id] < max(a[id<<1], a[(id<<1)|1])) { 428 if(a[id<<1] > a[(id << 1) | 1]) { 429 swap(a[id<<1], a[id]); 430 id <<= 1; 431 } 432 else { 433 swap(a[(id<<1)|1], a[id]); 434 id = (id << 1) | 1; 435 } 436 qq[qn++] = id; 437 } 438 if(id < (1 << g)) { 439 for(int i = qn - 1; i > 0; i--) { 440 a[qq[i]] = a[qq[i - 1]]; 441 } 442 a[qq[0]] = tmp; 443 return 0; 444 } 445 return tmp; 446 } 447 void solve() { 448 scanf("%d%d", &h, &g); 449 long long an = 0; 450 for(int i = 1; i < (1 << h); i++) { 451 scanf("%d", &a[i]); 452 an += a[i]; 453 } 454 int need = 0; 455 for(int i = 1; i < (1 << g); i++) { 456 while(1) { 457 int v = pull(i); 458 if(v) { 459 an -= v; 460 ops[need++] = i; 461 } 462 else break; 463 } 464 } 465 printf("%lld\n", an); 466 for(int i = 0; i < need; i++) printf("%d%c", ops[i], " \n"[i == need - 1]); 467 } 468 int main(){ 469 int T; 470 scanf("%d", &T); 471 while(T--) solve(); 472 return 0; 473 } 474 ``` 475 476 Tutorial is loading... 477 478 **author's code** 479 480 ``` 481 #include<bits/stdc++.h> 482 using namespace std; 483 const int SIZE = 2e5+10; 484 char s[SIZE]; 485 int cnt[SIZE]; 486 int cc[26]; 487 int all_cnt; 488 int ma; 489 void update_ma() { 490 while(ma > 0 && !cnt[ma]) ma--; 491 } 492 void dec1(int id) { 493 cnt[cc[id]]--; 494 cc[id]--; 495 cnt[cc[id]]++; 496 } 497 pair<int, int> stk[SIZE]; 498 int sn; 499 int m; 500 int now; 501 int last_len; 502 void add(int i, bool flag) { 503 if(flag) { 504 dec1(stk[sn - 1].second); 505 dec1(stk[i].second); 506 all_cnt -= 2; 507 printf("%d %d\n",now + 1, now + stk[i].first); 508 update_ma(); 509 sn--; 510 now -= stk[sn].first; 511 if(i + 1 < m) { 512 stk[i + 1].first += stk[sn].first; 513 } 514 else{ 515 last_len += stk[sn].first; 516 } 517 } 518 else { 519 stk[sn++] = stk[i]; 520 now += stk[i].first; 521 } 522 } 523 void solve(){ 524 scanf("%s", s); 525 int n = strlen(s); 526 all_cnt = 0; 527 int lt = 0; 528 m = 0; 529 for(int i = 1; i < n; i++) { 530 if(s[i] == s[i - 1]) { 531 cc[s[i] - 'a']++; 532 all_cnt++; 533 stk[m++] = make_pair(i - lt, (int)(s[i] - 'a')); 534 lt = i; 535 } 536 } 537 last_len = n - lt; 538 ma = 0; 539 for(int i = 0; i < 26; i++) { 540 cnt[cc[i]]++; 541 ma = max(ma, cc[i]); 542 } 543 printf("%d\n", 1 + max(ma, (all_cnt + 1) / 2)); 544 if(ma * 2 < all_cnt) { 545 sn = now = 0; 546 for(int i = 0; i < m; i++) { 547 add(i, sn && stk[sn - 1].second != stk[i].second && ma * 2 < all_cnt); 548 } 549 m = sn; 550 } 551 int main_id = -1; 552 for(int i = 0; i < 26; i++) { 553 if(cc[i] == ma) main_id = i; 554 } 555 sn = now = 0; 556 for(int i = 0; i < m; i++) { 557 add(i, sn && ((stk[sn - 1].second == main_id) ^ (stk[i].second == main_id))); 558 } 559 for(int i = 0; i < sn; i++) { 560 printf("%d %d\n",1 ,stk[i].first); 561 } 562 printf("%d %d\n", 1, last_len); 563 memset(cc, 0, sizeof(cc)); 564 memset(cnt, 0, sizeof(int) * (ma + 1)); 565 } 566 int main(){ 567 int T; 568 scanf("%d", &T); 569 for(int i = 1; i <= T; i++) solve(); 570 return 0; 571 } 572 ``` 573 574 Tutorial is loading... 575 576 **isaf27's solution** 577 578 ``` 579 //#pragma GCC optimize("O3") 580 #include <bits/stdc++.h> 581 582 using namespace std; 583 584 //defines 585 typedef long long ll; 586 typedef long double ld; 587 #define TIME clock() * 1.0 / CLOCKS_PER_SEC 588 #define prev _prev 589 #define y0 _y0 590 #define kill _kill 591 592 //permanent constants 593 const ld pi = acos(-1.0); 594 const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; 595 const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; 596 const int dx[4] = {0, 1, 0, -1}; 597 const int dy[4] = {1, 0, -1, 0}; 598 const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0}; 599 const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1}; 600 const int alf = 26; 601 const int dig = 10; 602 const int two = 2; 603 const int th = 3; 604 const ll prost = 239; 605 const ll btc = 30; 606 const ld eps = 1e-8; 607 const ll INF = (ll)(1e18 + 239); 608 const int BIG = (int)(1e9 + 239); 609 const int MOD = 1e9 + 7; // 610 611 //random 612 mt19937 rnd(239); //(chrono::high_resolution_clock::now().time_since_epoch().count()); 613 614 //constants 615 const int M = (int)(4e5 + 239); 616 const int N = (int)(2e3 + 239); 617 const int L = 20; 618 const int T = (1 << 18) + 239; 619 const int B = 500; 620 const int X = 210; 621 622 ll up(ll a, ll b) 623 { 624 return (a + b - 1) / b; 625 } 626 627 ll down(ll a, ll b) 628 { 629 return a / b; 630 } 631 632 int m; 633 ll l[M], n, k; 634 635 void solve() 636 { 637 cin >> n >> m >> k; 638 ll pr = 0; 639 for (int i = 0; i < m; i++) 640 { 641 ll p; 642 cin >> p; 643 l[i] = p - pr; 644 pr = p; 645 } 646 l[m++] = n - pr; 647 //for (int i = 0; i < m; i++) 648 // cerr << l[i] << " "; 649 //cerr << "\n"; 650 ll sum = k + m; 651 ll bl = 1; 652 ll br = n + 1; 653 while (br - bl > 1) 654 { 655 ll h = (bl + br) >> 1LL; 656 ll cur = 0; 657 for (int i = 0; i < m; i++) 658 cur += down(l[i], h); 659 if (sum <= cur) 660 bl = h; 661 else 662 br = h; 663 } 664 ll MIN = bl; 665 bl = 0; 666 br = n + 1; 667 while (br - bl > 1) 668 { 669 ll h = (bl + br) >> 1LL; 670 ll cur = 0; 671 for (int i = 0; i < m; i++) 672 cur += up(l[i], h); 673 if (sum >= cur) 674 br = h; 675 else 676 bl = h; 677 } 678 ll MAX = br; 679 vector<pair<ll, ll>> ban; 680 for (int i = 0; i < m; i++) 681 { 682 if (up(l[i], MAX) <= down(l[i], MIN)) 683 continue; 684 ll bl = 0; 685 ll br = MIN; 686 while (br - bl > 1) 687 { 688 ll h = (bl + br) >> 1LL; 689 if (down(l[i], h) == down(l[i], MIN)) 690 br = h; 691 else 692 bl = h; 693 } 694 ll first = MIN - br; 695 bl = MAX; 696 br = INF; 697 while (br - bl > 1) 698 { 699 ll h = (bl + br) >> 1LL; 700 if (up(l[i], MAX) == up(l[i], h)) 701 bl = h; 702 else 703 br = h; 704 } 705 ll second = bl - MAX; 706 ban.push_back(make_pair(first, second)); 707 } 708 ll add = MAX - MIN; 709 if (ban.empty()) 710 { 711 cout << add << "\n"; 712 return; 713 } 714 sort(ban.begin(), ban.end()); 715 vector<pair<ll, ll>> a; 716 for (int i = 0; i < (int)ban.size(); i++) 717 { 718 while (!a.empty() && a.back().second <= ban[i].second) 719 a.pop_back(); 720 a.push_back(ban[i]); 721 } 722 ll ans = INF; 723 ans = min(a[0].second + 1, ans); 724 ans = min(a.back().first + 1, ans); 725 for (int i = 0; i + 1 < (int)a.size(); i++) 726 ans = min(ans, a[i].first + a[i + 1].second + 2); 727 cout << ans + add << "\n"; 728 } 729 730 int32_t main() 731 { 732 #ifdef ONPC 733 freopen("input", "r", stdin); 734 #endif 735 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 736 int t; 737 cin >> t; 738 while (t--) 739 solve(); 740 return 0; 741 } 742 ``` 743 744 **author's solution** 745 746 ``` 747 /*{{{*/ 748 #include<cstdio> 749 #include<cstdlib> 750 #include<cstring> 751 #include<cmath> 752 #include<algorithm> 753 #include<string> 754 #include<iostream> 755 #include<sstream> 756 #include<set> 757 #include<map> 758 #include<queue> 759 #include<bitset> 760 #include<vector> 761 #include<limits.h> 762 #include<assert.h> 763 #define SZ(X) ((int)(X).size()) 764 #define ALL(X) (X).begin(), (X).end() 765 #define REP(I, N) for (int I = 0; I < (N); ++I) 766 #define REPP(I, A, B) for (int I = (A); I < (B); ++I) 767 #define FOR(I, A, B) for (int I = (A); I <= (B); ++I) 768 #define FORS(I, S) for (int I = 0; S[I]; ++I) 769 #define RS(X) scanf("%s", (X)) 770 #define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end())))) 771 #define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin()) 772 #define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++) 773 #define MP make_pair 774 #define PB push_back 775 #define MS0(X) memset((X), 0, sizeof((X))) 776 #define MS1(X) memset((X), -1, sizeof((X))) 777 #define LEN(X) strlen(X) 778 #define F first 779 #define S second 780 using namespace std; 781 typedef long long LL; 782 typedef unsigned long long ULL; 783 typedef long double LD; 784 typedef pair<int,int> PII; 785 typedef vector<int> VI; 786 typedef vector<LL> VL; 787 typedef vector<PII> VPII; 788 typedef pair<LL,LL> PLL; 789 typedef vector<PLL> VPLL; 790 template<class T> void _R(T &x) { cin >> x; } 791 void _R(int &x) { scanf("%d", &x); } 792 void _R(LL &x) { scanf("%lld", &x); } 793 void _R(double &x) { scanf("%lf", &x); } 794 void _R(char &x) { scanf(" %c", &x); } 795 void _R(char *x) { scanf("%s", x); } 796 void R() {} 797 template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); } 798 template<class T> void _W(const T &x) { cout << x; } 799 void _W(const int &x) { printf("%d", x); } 800 void _W(const LL &x) { printf("%lld", x); } 801 void _W(const double &x) { printf("%.16f", x); } 802 void _W(const char &x) { putchar(x); } 803 void _W(const char *x) { printf("%s", x); } 804 template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);} 805 template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); } 806 void W() {} 807 template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); } 808 #ifdef HOME 809 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");} 810 #else 811 #define DEBUG(...) 812 #endif 813 int MOD = 1e9+7; 814 void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;} 815 /*}}}*/ 816 const int SIZE = 1e6+10; 817 LL a[SIZE],num[SIZE]; 818 bool done[SIZE],be_added[SIZE]; 819 int n; 820 LL K; 821 LL get_upper_bound(int i){ 822 LL v=a[i]/num[i]; 823 if(v*num[i]!=a[i])v++; 824 return v; 825 } 826 LL get_next_upper_bound(int i){ 827 LL v=a[i]/(num[i]-1); 828 if(v*(num[i]-1)!=a[i])v++; 829 return v; 830 } 831 LL go(){ 832 if(K==n){ 833 return a[n-1]-a[0]; 834 } 835 LL ll=1,rr=a[n-1]; 836 while(ll<rr){ 837 LL mm=(ll+rr)/2; 838 LL need=0; 839 REP(i,n){ 840 if(a[i]>mm)need+=a[i]/mm; 841 else need++; 842 } 843 if(need>=K)ll=mm+1; 844 else rr=mm; 845 } 846 LL low=ll; 847 VPLL pp; 848 LL need=0; 849 REP(i,n){ 850 if(a[i]>=low){ 851 num[i]=a[i]/low; 852 pp.PB({a[i]/(num[i]+1),i}); 853 } 854 else { 855 num[i]=1; 856 } 857 need+=num[i]; 858 } 859 { 860 bool fail=0; 861 REP(i,n){ 862 if(get_upper_bound(i)>=low){ 863 fail=1; 864 break; 865 } 866 } 867 if(!fail) return low-1-min(low-1,a[0]); 868 } 869 REP(i,n){ 870 if(a[i]>=low&&a[i]/(num[i]+1)==low-1){ 871 LL v=a[i]/(low-1); 872 LL mi=min(v-num[i],K-need); 873 num[i]+=mi; 874 need+=mi; 875 if(need==K)break; 876 } 877 } 878 priority_queue<PLL,VPLL,greater<PLL>>added; 879 priority_queue<PLL>top; 880 LL mi=a[0]; 881 REP(i,n){ 882 if(num[i]>1){ 883 added.push(MP(get_next_upper_bound(i),i)); 884 } 885 top.push(MP(get_upper_bound(i),i)); 886 mi=min(mi,a[i]/num[i]); 887 } 888 LL an=top.top().F-mi; 889 REP(i,n)be_added[i]=done[i]=0; 890 LL ma=low-1; 891 while(!top.empty()&&!added.empty()){ 892 int id=top.top().S; 893 if(be_added[id])break; 894 done[id]=1; 895 top.pop(); 896 num[id]++; 897 mi=min(mi,a[id]/num[id]); 898 auto tmp=added.top(); 899 added.pop(); 900 if(done[tmp.S])break; 901 be_added[tmp.S]=1; 902 num[tmp.S]--; 903 if(num[tmp.S]>1)added.push({get_next_upper_bound(tmp.S),tmp.S}); 904 ma=max(ma,tmp.F); 905 an=min(an,(top.empty()?ma:max(ma,top.top().F))-mi); 906 } 907 return an; 908 } 909 void solve(){ 910 LL L; 911 //R(n,K,L); 912 R(L,n,K); 913 K+=n+1; 914 LL lt=0; 915 REP(i,n){ 916 LL x; 917 R(x); 918 a[i]=x-lt; 919 lt=x; 920 } 921 a[n++]=L-lt; 922 sort(a,a+n); 923 W(go()); 924 } 925 int main(){ 926 CASET{ 927 solve(); 928 } 929 return 0; 930 } 931 ```