QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#932351 | #10158. Forming Groups | Zawos | AC ✓ | 161ms | 54068kb | C++20 | 2.5kb | 2025-03-12 15:10:23 | 2025-03-12 15:10:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using vi = vector<int>;
using ii = pair<int, int>;
using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define all(x) x.begin(), x.end()
ll gcd(ll a, ll b) {return a == 0 ? b : gcd(b % a, a);}
int N;
const int M = 1e6;
void ckmin(pll &a, pll b) {
if (a.first * b.second > a.second * b.first)
a = b;
}
ll mx[2 * M], mn[2 * M];
void modify(int p, int value) {
int v = p;
for (mx[v += N] = value; v > 1; v >>= 1) mx[v>>1] = max(mx[v] , mx[v^1]);
v = p;
for (mn[v += N] = value; v > 1; v >>= 1) mn[v>>1] = min(mn[v] , mn[v^1]);
}
pll query(int l, int r) { // sum on interval [l, r)
ll ma = 0, mi = 1e9;
for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
if (l&1) {
mi = min(mi, mn[l]);
ma = max(ma, mx[l++]);
}
if (r&1) {
mi = min(mi, mn[r - 1]);
ma = max(ma, mx[--r]);
}
}
return {ma, mi};
}
pll solve(vll &nums, ll x, int k) {
if (k == 1) return {1e9, 1};
memset(mx, 0, 2 * k);
memset(mn, 0, 2 * k);
N = k;
vll sum(k);
int n = nums.size() + 1;
int cur = 1;
rep(i, 0, n - 1) {
sum[cur++] += nums[i];
if (cur == k) cur = 0;
}
sum[0] += x;
rep(i, 0, k)
modify(i, sum[i]);
pll ans = query(0, k);
cur = 0;
int nx = 1;
rep(i, 0, n - 1) {
sum[cur] += nums[i];
sum[cur] -= x;
sum[nx] -= nums[i];
sum[nx] += x;
modify(cur, sum[cur]);
modify(nx, sum[nx]);
ckmin(ans, query(0, k));
cur++;
nx++;
if (cur == k) cur = 0;
if (nx == k) nx = 0;
}
return ans;
}
void solve() {
int n; ll x;
cin >> n >> x;
vll nums(n - 1); rep(i, 0, n - 1) cin >> nums[i];
pll ans = {1e9, 1};
vi prime(n + 1, 1);
for (int i = 2; i <= n; i++) {
if (!prime[i]) continue;
for (int j = 2 * i; j <= n; j+= i)
prime[j] = 0;
if (n % i == 0)
ckmin(ans, solve(nums, x, i));
}
ll g = gcd(ans.first, ans.second);
cout << ans.first / g << " " << ans.second / g << "\n";
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--)
solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5860kb
input:
2 4 1 2 1 2 3 10 4 3
output:
1 1 10 3
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 59ms
memory: 5860kb
input:
100000 2 1 1 2 1 2 2 1 500 2 1 999 2 1 1000 2 1 549 2 2 1 2 2 2 2 2 500 2 2 999 2 2 1000 2 2 593 2 500 1 2 500 2 2 500 500 2 500 999 2 500 1000 2 500 715 2 999 1 2 999 2 2 999 500 2 999 999 2 999 1000 2 999 843 2 1000 1 2 1000 2 2 1000 500 2 1000 999 2 1000 1000 2 1000 603 2 857 1 2 857 2 2 857 500 ...
output:
1 1 2 1 500 1 999 1 1000 1 549 1 2 1 1 1 250 1 999 2 500 1 593 2 500 1 250 1 1 1 999 500 2 1 143 100 999 1 999 2 999 500 1 1 1000 999 333 281 1000 1 500 1 2 1 1000 999 1 1 1000 603 857 1 857 2 857 500 999 857 1000 857 857 545 1 1 2 1 500 1 999 1 1000 1 846 1 2 1 2 1 500 1 999 1 1000 1 424 1 500 1 50...
result:
ok 100000 lines
Test #3:
score: 0
Accepted
time: 66ms
memory: 17204kb
input:
1 1000000 67 627 234 606 150 424 912 663 161 575 254 40 911 528 558 979 471 736 834 591 675 396 98 657 606 70 42 363 512 471 859 506 386 921 495 434 602 568 107 566 509 787 508 543 528 351 235 632 529 125 880 443 465 808 35 801 896 160 490 436 750 975 138 977 265 767 868 522 738 738 982 526 212 505 ...
output:
31279955 31279937
result:
ok single line: '31279955 31279937'
Test #4:
score: 0
Accepted
time: 160ms
memory: 53968kb
input:
3 999983 355 543 755 432 260 724 226 810 135 594 454 570 636 988 738 345 427 535 367 266 3 148 16 728 798 662 827 355 904 722 774 885 998 430 797 793 745 451 790 320 596 517 229 635 159 390 921 450 991 451 658 830 401 170 746 443 156 695 60 663 703 575 624 748 672 586 498 483 77 547 264 285 137 509 ...
output:
1000 1 1644 1607 857 168
result:
ok 3 lines
Test #5:
score: 0
Accepted
time: 124ms
memory: 13924kb
input:
10 720720 552 786 415 984 76 180 178 861 235 817 298 756 965 523 221 551 633 125 562 443 10 264 318 585 809 134 243 726 928 880 601 762 464 629 808 477 58 702 358 108 680 359 499 541 762 301 710 464 979 254 1000 883 414 376 927 71 455 945 312 79 31 662 818 542 452 980 872 396 551 712 248 180 380 204...
output:
180502759 180502758 1 1 12840 11899 57277 57273 1 1 490 333 6632 6569 951 218 635 33 821 324
result:
ok 10 lines
Test #6:
score: 0
Accepted
time: 151ms
memory: 25800kb
input:
11 510510 691 739 829 620 614 406 541 577 951 331 135 792 769 871 6 482 532 912 512 502 221 809 90 850 967 531 875 635 731 537 499 554 595 42 903 259 649 758 864 102 625 28 443 678 647 748 384 582 958 122 116 211 376 236 863 566 891 18 1 691 625 183 327 400 3 888 248 556 961 612 456 288 600 755 776 ...
output:
1 1 1000 1 1000 1 236497 236491 2089867 2089856 1452432 1452431 926072 926071 101765 99318 45393 45391 104725 104724 13944 13925
result:
ok 11 lines
Test #7:
score: 0
Accepted
time: 148ms
memory: 16392kb
input:
12 930930 70 720 516 102 201 651 448 148 185 458 605 260 730 681 608 49 938 366 31 345 396 785 873 978 342 185 979 61 705 896 895 566 704 110 787 250 44 898 736 544 535 643 15 330 457 287 27 211 169 87 917 351 771 85 13 292 594 467 947 459 763 232 459 427 591 421 10 270 515 274 417 602 575 700 931 1...
output:
233045594 233045593 5963666 5960307 5491403 5491400 2391166 2391161 9159 8134 8782 8757 667 666 123 4 65 43 531 490 1209 1184 58 19
result:
ok 12 lines
Test #8:
score: 0
Accepted
time: 116ms
memory: 12324kb
input:
11 262096 791 651 352 445 56 216 838 520 467 400 360 60 200 531 689 555 876 386 295 464 319 113 416 650 15 667 829 946 563 194 820 319 968 919 253 904 493 788 298 666 650 284 38 548 769 321 212 318 996 761 367 982 726 950 553 532 882 975 639 468 407 598 259 265 267 99 278 767 247 11 68 934 218 345 3...
output:
65399646 65399645 94254225 94254224 1 1 20805977 20769712 1000 1 60921 60920 24833 24810 12878 9887 12747 12658 15339 15073 123 85
result:
ok 11 lines
Test #9:
score: 0
Accepted
time: 67ms
memory: 17068kb
input:
1 1000000 840 43 188 937 584 353 945 864 111 410 902 575 136 449 787 886 307 247 13 680 618 913 529 166 650 321 56 535 97 489 984 193 710 753 815 163 975 756 104 185 247 520 65 900 114 553 421 15 257 344 379 810 576 986 892 715 902 822 703 771 876 840 749 497 358 926 638 600 197 87 851 405 242 478 6...
output:
1 1
result:
ok single line: '1 1'
Test #10:
score: 0
Accepted
time: 154ms
memory: 54056kb
input:
4 999983 604 993 532 26 407 441 783 424 186 450 531 637 624 778 89 230 708 350 474 381 814 257 266 245 256 565 454 842 634 885 732 165 689 246 273 281 780 147 736 345 424 100 412 266 987 774 658 549 831 767 341 305 676 708 25 449 753 165 246 595 473 780 309 888 694 285 752 674 755 839 618 792 268 54...
output:
1000 1 2770 2683 715 219 651 113
result:
ok 4 lines
Test #11:
score: 0
Accepted
time: 124ms
memory: 13928kb
input:
6 720720 123 172 240 648 85 215 42 958 564 666 374 596 912 671 738 366 889 350 764 755 54 84 356 685 652 530 68 609 183 39 538 485 202 834 937 744 464 343 575 337 924 885 521 779 326 643 435 853 634 633 723 139 107 170 613 356 909 856 829 213 972 100 657 158 385 301 845 760 464 287 400 516 40 759 51...
output:
1 1 69525135 69525134 500 1 48441 47762 1749 1345 674 15
result:
ok 6 lines
Test #12:
score: 0
Accepted
time: 136ms
memory: 13648kb
input:
9 510510 218 598 365 992 44 117 831 788 718 179 936 662 450 925 1000 884 848 694 987 384 340 520 458 626 235 485 760 98 74 895 451 840 981 159 67 954 247 393 395 160 149 241 841 11 483 783 278 931 378 464 266 162 885 789 339 561 793 707 298 731 424 680 709 630 292 841 216 594 985 351 666 21 439 266 ...
output:
63876787 63876785 1000 1 3748632 3672229 11936074 11936073 6693343 6693341 3026805 3026804 1000 1 169591 169072 498 31
result:
ok 9 lines
Test #13:
score: 0
Accepted
time: 67ms
memory: 17112kb
input:
1 1000000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 ...
output:
1 1
result:
ok single line: '1 1'
Test #14:
score: 0
Accepted
time: 150ms
memory: 16388kb
input:
14 930930 940 387 435 975 562 229 653 873 406 919 33 566 406 154 429 356 483 231 515 311 905 486 791 931 848 788 52 325 938 493 270 43 349 996 170 406 842 713 579 308 209 67 394 411 779 847 746 163 965 898 866 530 334 623 795 355 750 908 418 853 393 525 557 621 454 711 56 325 716 881 983 726 787 520...
output:
232905069 232905068 7228429 7228428 282165 282164 766229 738134 1000 1 1000 1 128578 128449 192912 192911 28048 28047 44151 44077 972 25 233 34 897 656 1325 851
result:
ok 14 lines
Test #15:
score: 0
Accepted
time: 133ms
memory: 23972kb
input:
13 62029 879 772 361 631 872 31 664 979 793 388 549 847 960 374 961 899 454 441 805 765 990 911 740 865 452 433 194 15 110 126 16 422 905 400 955 822 605 695 465 334 769 66 45 468 144 958 422 113 374 326 126 924 403 194 419 331 883 128 727 522 219 356 903 980 684 23 519 465 807 257 425 759 701 755 5...
output:
2833628 2801749 96413719 96413718 1000 1 22223131 22223130 315647 312306 1677422 1677419 198401 175465 1 1 11665 11664 142614 138937 5293 4993 69 34 161 107
result:
ok 13 lines
Test #16:
score: 0
Accepted
time: 67ms
memory: 17204kb
input:
1 1000000 192 349 880 229 96 975 522 798 113 403 567 437 368 420 745 449 461 561 363 370 925 977 341 273 690 248 278 104 288 598 293 773 850 620 63 925 671 862 310 840 27 513 795 785 928 930 710 264 467 946 805 846 831 631 572 819 360 418 311 282 402 309 624 913 223 233 122 565 475 945 775 648 436 4...
output:
250464492 250464485
result:
ok single line: '250464492 250464485'
Test #17:
score: 0
Accepted
time: 153ms
memory: 54068kb
input:
5 999983 603 720 289 412 863 344 752 299 632 112 951 607 454 253 971 250 314 507 927 462 897 433 877 976 698 991 236 260 820 285 370 126 630 782 728 670 159 738 191 900 828 866 402 598 526 878 360 222 371 243 157 846 355 259 291 122 382 607 505 707 120 409 946 633 292 98 870 897 722 159 894 887 58 8...
output:
1000 1 2680 2409 309 173 619 20 923 243
result:
ok 5 lines
Test #18:
score: 0
Accepted
time: 123ms
memory: 13928kb
input:
5 720720 798 262 702 767 159 918 710 932 947 142 136 289 581 793 414 252 791 968 398 941 124 661 555 355 213 95 711 56 318 40 425 187 297 732 367 62 395 190 14 842 274 940 627 518 891 11 640 456 594 685 586 173 345 343 807 162 723 668 885 533 554 14 953 858 177 67 34 448 680 106 48 253 873 591 785 7...
output:
180554954 180554953 69425960 69425959 474525 474484 37412 37377 989 637
result:
ok 5 lines
Test #19:
score: 0
Accepted
time: 133ms
memory: 11460kb
input:
19 510510 472 957 692 765 118 291 19 113 919 597 51 414 156 182 807 187 338 457 985 973 703 338 325 617 79 511 42 953 767 109 193 154 778 585 78 824 947 991 712 243 806 386 390 747 815 471 612 649 638 37 402 33 212 754 366 705 886 128 493 939 692 961 811 279 12 600 633 129 312 74 715 28 960 648 521 ...
output:
127632259 127632258 1 1 19291124 19291105 1724236 1716163 3718929 3718925 391977 391966 874255 839592 560179 560165 442653 442612 227004 224069 494 7 60745 60737 386 107 2796 2207 643 565 993 56 3830 3747 9017 8871 2101 2027
result:
ok 19 lines
Test #20:
score: 0
Accepted
time: 161ms
memory: 16284kb
input:
13 930930 352 783 776 84 361 442 279 329 596 236 11 925 534 19 102 785 949 848 860 764 280 730 766 140 942 657 27 207 906 861 660 819 910 852 840 826 254 320 245 80 172 489 566 691 850 586 771 784 904 270 748 889 426 528 752 325 101 825 387 451 351 295 143 146 467 596 124 256 684 215 498 458 569 869...
output:
1 1 1210057 1207055 7446157 7446155 218893 218876 2503801 2458194 578981 578650 26527 25498 1529 1516 999 4 7681 7530 153493 153492 9694 9681 489 2
result:
ok 13 lines
Test #21:
score: 0
Accepted
time: 126ms
memory: 17736kb
input:
11 808258 659 468 117 863 271 456 466 19 860 28 329 632 951 391 646 554 426 917 592 157 471 322 276 492 599 963 454 160 855 1 997 931 918 684 594 46 113 891 187 523 975 37 376 562 217 483 218 60 969 701 815 341 332 379 782 866 83 302 872 877 903 992 356 518 522 760 77 145 342 143 702 511 140 195 288...
output:
202086080 202086079 23726756 23726657 871730 871697 1391913 1388638 1307807 1284160 1 1 91271 78130 1000 1 18008 17737 8939 8936 301 11
result:
ok 11 lines