QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#182755#5740. Testing Subjects Usually Dieucup-team1209#RE 444ms10328kbC++202.1kb2023-09-18 15:04:222023-09-18 15:04:23

Judging History

你现在查看的是最新测评结果

  • [2023-09-18 15:04:23]
  • 评测
  • 测评结果:RE
  • 用时:444ms
  • 内存:10328kb
  • [2023-09-18 15:04:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,y,x) for (int i=(y);i>=(x);i--)
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
#define templ template<typename T>
templ bool chkmin(T &x,T y){return x>y?x=y,1:0;}
templ bool chkmax(T &x,T y){return x<y?x=y,1:0;}
void file() {
    #ifdef zqj
    freopen("a.in","r",stdin);
    #endif
}
typedef long long ll;
typedef double db;
#define sz 101010

int n; db c;
db p[sz];

db calc(vector<db>k,vector<db>b) {
    vector<int>id(n);
    vector<db>tt(n);
    rep(i,0,n-1) id[i]=i,chkmax(b[i],1e-114),tt[i]=k[i]/b[i]/b[i];
    sort(id.begin(),id.end(),[&](int x,int y){return tt[x]<tt[y];});
    db s1=0,s2=0;
    for (auto kk:k) s1+=sqrt(1/kk);
    rep(i,0,n-1) s2+=b[i]/k[i];
    s2++;
    db C=s1/s2;
    int L=0;
    while (233) {
        if (C*C<tt[id[L]]) break;
        assert(L!=n-1);
        int x=id[L];
        s1-=sqrt(1/k[x]),s2-=b[x]/k[x];
        C=s1/s2;
        ++L;
    }
    C=C*C;
    vector<db>x(L);
    db s3=0;
    rep(i,L,n-1) x.push_back({(sqrt(k[id[i]]/C)-b[id[i]])/k[id[i]]}),s3+=x.back();
    assert(fabs(s3-1)<1e-8);
    db res=0;
    rep(i,0,n-1) res+=1/(k[id[i]]*x[i]+b[id[i]]);
    return res;
}

db check(db a) {
    vector<db>k,b;
    db res=0;
    rep(i,1,n) {
        res-=p[i]*c*a/(1-c);
        db K=(1-c)*(1-c),B=(1-c)*c;
        K/=p[i],B/=p[i];
        K/=(1+c*a-c),B/=(1+c*a-c);
        k.push_back(K),b.push_back(B);
    }
    res+=calc(k,b);
    return res;
}

int main() {
    file();
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n>>c;
    rep(i,1,n) cin>>p[i],p[sz-1]+=p[i];
    rep(i,1,n) p[i]/=p[sz-1];
    if (c==100) {
        db mx=0;
        rep(i,1,n) chkmax(mx,p[i]);
        cout<<setprecision(10)<<fixed<<1/mx<<'\n';
        return 0;
    }
    // TODO: c=0?
    c/=100;
    db l=0,r=n;
    rep(i,1,55) {
        db m=(l+r)/2;
        if (check(m)<=m) r=m;
        else l=m;
    }
    cout<<setprecision(10)<<fixed<<(l+r)/2<<'\n';
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3916kb

input:

4 100
25 25 25 25

output:

4.0000000000

result:

ok found '4.0000000', expected '4.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

2 0
1 4

output:

1.8000000000

result:

ok found '1.8000000', expected '1.8000000', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4036kb

input:

5 0
245 802 95 452 756

output:

4.4685309985

result:

ok found '4.4685310', expected '4.4685310', error '0.0000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

5 10
85 144 62 67 925

output:

3.0823373302

result:

ok found '3.0823373', expected '3.0823373', error '0.0000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

5 20
573 598 705 893 279

output:

4.6655640734

result:

ok found '4.6655641', expected '4.6655641', error '0.0000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

5 25
533 195 166 109 527

output:

3.9338079305

result:

ok found '3.9338079', expected '3.9338079', error '0.0000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

5 50
498 942 71 637 663

output:

3.8718857359

result:

ok found '3.8718857', expected '3.8718857', error '0.0000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3912kb

input:

5 75
971 663 827 333 382

output:

3.7488898765

result:

ok found '3.7488899', expected '3.7488899', error '0.0000000'

Test #9:

score: 0
Accepted
time: 0ms
memory: 4044kb

input:

5 90
736 303 722 239 696

output:

3.7688203284

result:

ok found '3.7688203', expected '3.7688203', error '0.0000000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

100 3
658 202 750 953 273 250 658 749 723 227 147 300 891 268 626 9 436 76 199 550 256 668 646 520 736 830 147 712 696 56 668 685 705 170 384 262 264 645 453 806 436 145 575 485 77 871 716 408 536 245 952 385 469 776 647 262 951 784 314 270 122 969 179 635 513 444 709 576 887 834 131 422 334 978 875...

output:

76.0238805989

result:

ok found '76.0238806', expected '76.0238806', error '0.0000000'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

100 7
732 702 802 720 694 714 45 298 555 362 471 319 538 926 146 669 947 210 436 4 652 273 408 91 25 626 687 586 747 415 823 623 364 487 26 256 149 606 458 173 254 99 191 44 829 789 17 894 353 597 809 880 651 126 465 288 369 544 136 703 805 231 305 81 680 753 592 293 374 273 504 884 257 480 588 819 ...

output:

68.6886434926

result:

ok found '68.6886435', expected '68.6886435', error '0.0000000'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3952kb

input:

100 93
769 488 41 386 28 822 145 782 981 94 665 928 187 344 956 992 367 530 899 499 292 151 791 309 21 35 756 41 592 65 788 914 497 961 69 170 535 586 853 192 497 346 8 723 71 838 545 628 806 937 128 436 310 917 956 490 483 984 799 865 116 643 803 301 407 358 187 699 128 271 444 887 904 22 556 301 9...

output:

51.1578081600

result:

ok found '51.1578082', expected '51.1578082', error '0.0000000'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3984kb

input:

100 99
725 12 862 184 81 723 289 915 414 919 360 251 232 295 807 305 968 480 324 666 87 348 117 25 51 447 976 795 598 372 153 661 949 409 974 911 915 801 569 138 682 431 604 172 249 50 890 337 471 828 451 856 627 349 247 487 649 223 882 48 470 177 556 258 744 930 101 763 817 332 54 187 707 521 989 5...

output:

51.3845849417

result:

ok found '51.3845849', expected '51.3845849', error '0.0000000'

Test #14:

score: 0
Accepted
time: 0ms
memory: 4036kb

input:

100 100
532 836 32 963 414 408 831 402 576 222 72 344 242 723 191 935 946 78 364 548 702 486 549 801 659 734 380 776 800 458 146 772 656 979 849 148 283 106 728 506 295 58 873 927 471 416 649 662 279 990 437 554 644 733 542 686 915 478 787 209 504 522 646 309 266 66 214 592 290 563 262 524 434 655 1...

output:

51.4595959596

result:

ok found '51.4595960', expected '51.4596000', error '0.0000001'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3920kb

input:

100 47
785 718 467 35 21 369 753 590 885 262 654 601 756 172 535 746 617 609 42 358 845 102 722 370 195 113 745 321 804 73 264 941 168 8 920 559 814 736 636 302 524 814 39 24 949 720 550 507 476 990 687 790 497 259 410 815 377 474 214 612 24 852 762 804 654 738 219 323 427 56 430 35 553 620 922 298 ...

output:

57.1909300350

result:

ok found '57.1909300', expected '57.1909300', error '0.0000000'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

100 23
316 896 76 266 69 253 305 63 629 226 429 333 173 252 563 843 473 599 725 31 993 600 16 651 181 885 911 23 50 882 155 314 223 761 913 743 783 185 874 433 425 987 637 683 848 590 273 193 97 86 836 189 307 722 5 36 954 567 54 357 413 923 963 128 862 235 238 395 699 558 287 782 749 495 983 57 881...

output:

58.7401469468

result:

ok found '58.7401469', expected '58.7401469', error '0.0000000'

Test #17:

score: 0
Accepted
time: 1ms
memory: 3924kb

input:

100 79
75 171 854 903 856 955 77 209 460 230 261 266 235 312 703 808 967 903 168 305 554 554 164 452 613 104 107 217 481 394 478 663 545 994 190 668 832 244 342 490 509 910 52 922 548 405 713 795 792 522 173 337 964 571 963 988 274 472 415 126 418 247 453 103 265 137 133 533 583 468 860 810 799 919 ...

output:

51.6881155059

result:

ok found '51.6881155', expected '51.6881155', error '0.0000000'

Test #18:

score: 0
Accepted
time: 2ms
memory: 3904kb

input:

1000 0
255 862 615 652 905 237 800 500 35 648 990 91 27 877 913 715 541 374 599 163 251 476 381 750 458 706 546 924 112 924 319 47 432 994 164 314 323 822 732 881 131 4 914 386 402 907 660 934 585 379 766 387 837 95 547 130 875 931 847 346 25 800 270 144 699 417 904 608 823 785 827 643 744 813 537 3...

output:

893.8102525070

result:

ok found '893.8102525', expected '893.8102525', error '0.0000000'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3952kb

input:

1000 10
40 638 938 226 578 478 634 337 539 175 527 985 361 510 337 323 358 357 75 748 129 205 326 747 725 706 228 371 771 18 821 255 284 330 622 886 995 359 354 262 591 613 850 766 610 653 616 739 691 357 396 781 954 757 615 960 922 449 739 14 486 472 922 328 866 429 705 893 634 263 231 857 867 225 ...

output:

556.4757122002

result:

ok found '556.4757122', expected '556.4757122', error '0.0000000'

Test #20:

score: 0
Accepted
time: 2ms
memory: 3772kb

input:

1000 20
661 481 103 543 806 209 681 171 44 106 335 829 408 339 167 930 416 1000 896 164 246 696 891 978 696 170 137 423 871 837 322 806 965 126 121 900 859 819 668 293 714 508 609 192 53 470 605 65 981 442 931 350 745 955 997 858 969 697 591 63 651 441 719 738 373 775 117 907 452 447 785 258 824 973...

output:

543.1299213612

result:

ok found '543.1299214', expected '543.1299214', error '0.0000000'

Test #21:

score: 0
Accepted
time: 0ms
memory: 4024kb

input:

1000 25
185 794 825 463 270 775 648 695 952 22 752 348 525 546 469 669 274 397 497 943 95 178 365 387 242 924 43 183 660 999 898 204 329 495 814 224 774 130 459 696 596 328 491 986 48 603 718 782 30 31 569 471 712 226 917 701 128 462 580 297 795 965 372 565 278 569 404 75 315 513 824 504 203 524 546...

output:

529.5788799235

result:

ok found '529.5788799', expected '529.5788799', error '0.0000000'

Test #22:

score: 0
Accepted
time: 2ms
memory: 3916kb

input:

1000 50
241 223 609 18 575 13 616 101 264 541 356 413 709 126 767 772 504 370 840 269 264 199 701 698 471 204 588 854 699 150 880 517 760 722 167 756 93 856 166 923 720 61 426 182 277 681 254 865 743 418 811 500 759 744 599 881 806 529 781 882 193 975 156 623 818 740 413 34 156 278 106 229 441 438 5...

output:

519.1343836743

result:

ok found '519.1343837', expected '519.1343837', error '0.0000000'

Test #23:

score: 0
Accepted
time: 2ms
memory: 4108kb

input:

1000 75
10 589 345 900 100 698 776 404 378 87 787 772 627 103 571 120 321 867 495 866 173 92 560 825 242 554 757 137 762 691 535 454 414 84 446 1000 116 119 277 17 585 460 753 861 492 138 727 973 492 767 291 191 123 516 281 909 818 322 98 660 268 565 275 759 708 431 919 519 414 862 55 418 350 409 23...

output:

501.4733837764

result:

ok found '501.4733838', expected '501.4733838', error '0.0000000'

Test #24:

score: 0
Accepted
time: 2ms
memory: 3900kb

input:

1000 90
751 611 489 19 184 10 360 548 330 115 238 270 755 448 879 570 573 43 63 567 344 977 937 64 450 157 94 914 452 875 804 647 229 637 331 462 429 189 876 987 776 119 414 637 336 453 144 122 144 952 456 83 985 498 254 575 709 76 843 150 434 249 852 502 984 886 16 954 60 128 401 658 65 774 244 810...

output:

488.5650480500

result:

ok found '488.5650480', expected '488.5650481', error '0.0000000'

Test #25:

score: 0
Accepted
time: 0ms
memory: 3948kb

input:

1000 3
903 508 536 772 440 934 505 818 91 374 780 929 258 177 763 73 78 398 386 623 127 219 673 826 672 422 23 101 847 34 519 202 630 591 248 526 410 775 719 616 907 331 82 846 524 764 555 122 377 746 688 769 906 197 615 352 242 34 740 806 601 294 769 729 909 229 824 710 897 498 807 263 337 108 378 ...

output:

627.6566438881

result:

ok found '627.6566439', expected '627.6566439', error '0.0000000'

Test #26:

score: 0
Accepted
time: 2ms
memory: 3892kb

input:

1000 7
100 854 58 604 988 576 86 197 836 523 675 272 146 550 432 994 953 541 189 103 706 977 829 972 210 897 134 668 5 994 377 972 670 890 316 477 114 224 220 744 353 667 843 144 288 43 427 266 906 810 386 547 641 563 627 871 138 2 319 238 404 338 224 770 379 687 328 258 213 482 966 941 887 824 883 ...

output:

552.8917511500

result:

ok found '552.8917512', expected '552.8917511', error '0.0000000'

Test #27:

score: 0
Accepted
time: 2ms
memory: 4016kb

input:

1000 93
895 818 184 678 275 454 634 347 573 355 948 617 441 217 492 761 73 170 107 587 504 645 216 808 433 331 879 745 232 724 567 657 519 976 725 166 76 678 192 335 982 281 949 527 175 955 785 882 576 539 140 385 599 390 676 790 232 306 116 704 149 642 539 240 665 43 138 112 381 632 655 677 375 170...

output:

508.7550924230

result:

ok found '508.7550924', expected '508.7550925', error '0.0000000'

Test #28:

score: 0
Accepted
time: 2ms
memory: 4016kb

input:

1000 99
552 468 534 484 878 913 529 892 756 66 582 586 782 821 355 122 281 285 197 581 964 993 73 448 271 632 83 481 418 750 961 721 585 271 596 212 715 436 501 688 856 391 260 93 657 494 653 107 179 323 711 217 202 227 848 455 650 230 872 728 845 508 974 123 998 988 943 69 146 582 57 494 416 186 43...

output:

493.7421669614

result:

ok found '493.7421670', expected '493.7421669', error '0.0000000'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3892kb

input:

1000 100
925 680 759 233 463 643 479 53 186 140 73 576 129 231 156 292 143 807 104 509 115 599 889 405 877 566 807 326 768 183 925 955 129 182 220 885 357 792 548 632 691 941 802 683 612 441 343 924 26 906 870 876 212 809 350 430 834 749 677 799 270 571 177 644 464 489 132 33 285 953 632 932 422 92 ...

output:

503.0710000000

result:

ok found '503.0710000', expected '503.0710000', error '0.0000000'

Test #30:

score: 0
Accepted
time: 2ms
memory: 3900kb

input:

1000 47
162 298 475 310 802 473 488 340 969 425 62 905 482 710 159 871 644 506 126 485 584 925 682 857 437 675 382 227 924 921 593 654 305 287 70 885 123 927 354 771 550 993 198 741 250 778 750 383 710 733 592 706 251 193 249 100 759 523 666 260 836 835 283 447 108 23 740 366 74 895 981 556 965 164 ...

output:

523.5929308158

result:

ok found '523.5929308', expected '523.5929308', error '0.0000000'

Test #31:

score: 0
Accepted
time: 2ms
memory: 3956kb

input:

1000 23
131 662 34 186 528 457 133 950 642 817 271 988 601 860 75 910 44 961 225 627 446 191 452 454 271 638 512 466 42 596 437 252 583 295 67 675 838 438 694 520 694 97 544 639 591 438 762 947 754 186 414 677 847 460 863 323 273 261 282 98 345 670 963 587 302 264 177 95 454 649 329 164 877 160 499 ...

output:

539.6438528323

result:

ok found '539.6438528', expected '539.6438528', error '0.0000000'

Test #32:

score: 0
Accepted
time: 2ms
memory: 4120kb

input:

1000 79
529 135 855 239 519 892 231 53 170 562 564 312 176 154 103 709 572 731 222 924 965 796 696 907 816 805 579 929 755 945 580 472 250 203 540 479 414 501 393 767 430 734 283 42 893 562 761 711 616 278 705 965 888 632 773 826 504 815 273 712 536 432 76 795 199 694 496 154 349 832 816 9 260 85 78...

output:

523.7913828696

result:

ok found '523.7913829', expected '523.7913829', error '0.0000000'

Test #33:

score: 0
Accepted
time: 444ms
memory: 10328kb

input:

100000 0
934 224 590 770 321 912 370 669 958 692 314 802 232 895 944 814 490 923 892 850 671 72 336 967 780 448 848 582 529 797 285 320 978 249 561 187 317 60 843 475 660 749 637 821 171 699 231 951 156 771 891 14 527 302 571 193 453 558 598 263 617 121 976 926 824 883 681 374 738 890 695 602 409 14...

output:

88990.4998875308

result:

ok found '88990.4998875', expected '88990.4998875', error '0.0000000'

Test #34:

score: -100
Runtime Error

input:

100000 10
842 872 627 449 670 854 956 983 724 845 393 511 191 879 602 246 807 59 370 723 512 963 878 34 744 453 520 773 815 472 263 23 929 912 811 923 908 137 925 729 360 264 453 172 759 806 843 779 188 664 51 528 29 332 214 652 646 572 302 795 315 20 426 336 911 668 938 163 607 939 222 804 147 823 ...

output:


result: