QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#932351#10158. Forming GroupsZawosAC ✓161ms54068kbC++202.5kb2025-03-12 15:10:232025-03-12 15:10:23

Judging History

This is the latest submission verdict.

  • [2025-03-12 15:10:23]
  • Judged
  • Verdict: AC
  • Time: 161ms
  • Memory: 54068kb
  • [2025-03-12 15:10:23]
  • Submitted

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