QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#488410#4568. Budget Distributionarnold518WA 89ms9896kbC++172.9kb2024-07-24 01:35:532024-07-24 01:35:54

Judging History

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

  • [2024-07-24 01:35:54]
  • 评测
  • 测评结果:WA
  • 用时:89ms
  • 内存:9896kb
  • [2024-07-24 01:35:53]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

typedef long double ld;
typedef pair<ld, ld> pdd;

const int MAXN = 5e4;
const int MAXQ = 3e5;

const ld eps = 1e-10;

int N, Q;
vector<pll> A[MAXN+10];
pll B[MAXQ+10];
ld xsum, sqcsum, fsum, psum;
ld ans[MAXN+10];

struct Data
{
    ld slp, dsqc, dx;
    ld dp, df;
    bool operator < (Data ot) const { return slp < ot.slp; }
};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    ll sum=0;
    scanf("%d%d", &N, &Q);

    vector<Data> V;
    for(int i=1; i<=N; i++)
    {
        int t;
        scanf("%d", &t);
        A[i]=vector<pll>(t);

        ll psum=0, csum=0;
        for(int j=0; j<t; j++) scanf("%lld", &A[i][j].first), csum+=A[i][j].first;
        for(int j=0; j<t; j++) scanf("%lld", &A[i][j].second), psum+=A[i][j].second;
        sum+=csum;

        sort(A[i].begin(), A[i].end(), [&](pll p, pll q)
        {
            return p.first*q.second < q.first*p.second;
        });

        ld bef=0;
        ll cval=csum, pval=psum;
        bool flag=false;
        for(int j=0; j<t; j++)
        {
            ld l=bef, r=(ld)A[i][j].first/A[i][j].second*psum;
            l=max(l, (ld)csum);
            if(l+eps < r)
            {
                ld slpl = -cval/l/l, slpr = -cval/r/r;
                ld fl = cval/l-(ld)pval/psum, fr = cval/r-(ld)pval/psum;
                // printf("%.10Lf %.10Lf : %.10Lf %.10Lf / %.10Lf %.10Lf / %lld %lld %lld\n", l, r, slpl, slpr, fl, fr, cval, pval, psum);
                if(!flag)
                {
                    flag=true;
                    xsum+=l;
                    fsum+=fl;
                }
                V.push_back({slpl, sqrt((ld)cval), -l, (ld)pval/psum, -fl});
                V.push_back({slpr, -sqrt((ld)cval), r, -(ld)pval/psum, fr});
            }

            cval-=A[i][j].first;
            pval-=A[i][j].second;
            bef=r;
        }
        if(!flag) xsum+=max(bef, (ld)csum);
    }
    for(int i=1; i<=Q; i++)
    {
        scanf("%lld", &B[i].first);
        B[i].first+=sum;
        B[i].second=i;
    }
    sort(B+1, B+Q+1);

    sort(V.begin(), V.end());
    for(int i=0, j=1; i<V.size(); i++)
    {
        auto [slp, dsqc, dx, dp, df] = V[i];
        ld x=(sqcsum+dsqc)/sqrt(-slp)+(xsum+dx);
        // printf("!%.20Lf : %.20Lf\n", slp, x);
        for(; j<=Q && B[j].first<=x; j++)
        {
            // printf("ANS %lld %lld => %.10Lf %.10Lf %.10Lf\n", B[j].second, B[j].first, sqcsum, psum, fsum);
            if(sqcsum < eps) ans[B[j].second]=fsum;
            else ans[B[j].second]=sqcsum*sqcsum/(B[j].first-xsum)-psum+fsum;
        }

        sqcsum+=dsqc;
        xsum+=dx;
        fsum+=df;
        psum+=dp;
    }

    for(int i=1; i<=Q; i++) printf("%.20Lf\n", ans[i]*2);
}

詳細信息

Test #1:

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

input:

1 5
3 1 7 10 700 400 100
0 2 10 50 102

output:

1.05555555555555555551
0.86666666666666666651
0.54761904761904761906
0.12745098039215686281
0.00000000000000000005

result:

ok 5 numbers

Test #2:

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

input:

2 5
3 10 70 100 700 400 100
3 10 30 100 700 400 100
2 10 50 70 110

output:

2.29670329670329670347
2.21677634065518756683
1.86901673626003215416
1.73015873015873015853
1.52713178294573643417

result:

ok 5 numbers

Test #3:

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

input:

10 10
2 33942 868 371 78
2 76858 41608 333 100
2 6654 20321 170 203
2 2620 63358 632 53
2 93065 61561 594 212
2 57474 542 813 559
2 40721 17760 290 976
2 46703 85826 255 366
2 46854 97247 875 814
2 86728 83989 602 306
201032820943 922351084935 360042197511 441040805811 822857993607 196200869890 4856...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000

result:

ok 10 numbers

Test #4:

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

input:

10 10
2 96134 53888 702 380
2 13325 18733 529 846
2 88540 54362 938 703
2 8808 55334 591 19
2 44013 54721 319 891
2 83136 55364 214 73
2 20391 6867 838 8
2 26623 38206 497 763
2 17952 8445 377 586
2 44642 45084 728 45
79 70 52 33 63 42 12 63 43 19

output:

4.47092640798093454409
4.47138754315995747392
4.47231075500160071834
4.47328662061820361709
4.47174642073196838181
4.47282419364680018659
4.47436684259907563191
4.47174642073196838181
4.47277283230517053170
4.47400657777277784097

result:

ok 10 numbers

Test #5:

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

input:

10 10
2 87040 85595 968 661
2 30804 2371 595 360
2 67653 67814 918 546
2 41321 35253 782 456
2 87902 48810 187 121
2 42170 84373 530 949
2 50987 54778 671 987
2 14728 42286 11 621
2 58533 75318 331 777
2 16391 57471 903 6
59864 120 8708 29592 32313 33728 70753 22703 10343 23788

output:

2.60343780003182455308
3.80230065581593389308
3.42288753536892115356
2.96016813271937869302
2.92026983039578633735
2.90046122302335462667
2.49844328844343501177
3.07327149176194822284
3.36762279199016834530
3.05418759781712122756

result:

ok 10 numbers

Test #6:

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

input:

10 10
2 55721 79321 580 343
2 95806 49722 805 940
2 78827 17939 667 94
2 6559 95072 787 101
2 94219 75884 552 449
2 30793 62126 870 399
2 85442 23970 408 302
2 1278 2598 862 62
2 31318 32132 323 412
2 58132 71731 139 922
3906840 989184 7399265 8741239 2517664 9283266 5589494 6287477 4787549 4589132

output:

0.00000000000000000000
0.22562556533133194457
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000

result:

ok 10 numbers

Test #7:

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

input:

10 1000
2 77028 12264 551 939
2 78089 30777 523 797
2 52960 82253 148 858
2 31700 74778 830 751
2 82878 16882 965 56
2 45145 65715 165 802
2 45515 12564 949 925
2 74172 24959 285 684
2 82124 35743 748 30
2 57875 4015 855 611
735264331681 371600467165 94562142784 569058824359 478028793676 54038716428...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 1000 numbers

Test #8:

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

input:

10 1000
2 3938 22415 871 82
2 27631 97743 165 825
2 65967 18034 62 901
2 32242 10555 911 686
2 8940 50904 300 731
2 68995 92862 315 731
2 88209 67039 379 38
2 21342 97668 185 932
2 87548 79592 402 31
2 58250 93518 738 332
1 95 82 41 37 90 75 42 76 12 57 100 26 41 85 6 15 37 34 61 42 51 69 5 14 30 76...

output:

6.10739851392914860585
6.10135266606346796494
6.10218623196396171664
6.10482054917004762426
6.10507799397209895923
6.10167317133866879365
6.10263541481360199123
6.10475620016146517744
6.10257123126722576681
6.10668879382639038069
6.10379154980221199723
6.10103228194854203944
6.10578636975547562465
6...

result:

ok 1000 numbers

Test #9:

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

input:

10 1000
2 5140 93191 993 507
2 49021 71125 253 668
2 54110 90050 237 705
2 14347 68749 921 989
2 90266 34358 823 341
2 75716 40108 379 298
2 75242 1960 390 505
2 82368 59940 873 599
2 80119 25572 458 269
2 77505 23084 473 542
13582 50935 29056 56674 60779 57858 54777 64188 71802 62584 98903 19513 26...

output:

4.25314670483105375202
3.62459972041897065804
3.97311847478146721994
3.54016727012256042094
3.48116929613913928020
3.52303734110361567639
3.56781702564544696819
3.43290250523067033608
3.32731273049610648063
3.45553524606459716790
2.97462098848839042115
4.14213269441308574483
4.02466255299675230214
3...

result:

ok 1000 numbers

Test #10:

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

input:

10 1000
2 63317 53050 130 281
2 64560 28892 410 881
2 1063 11155 826 49
2 40055 59506 424 645
2 12471 7521 963 271
2 19232 77975 924 545
2 99920 71689 222 682
2 94741 8756 840 370
2 48868 73259 816 882
2 66849 33301 483 146
9873316 4084979 2160366 7640555 1658999 4484798 3942725 8537680 7071378 1801...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
1.77966520361220030891
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 1000 numbers

Test #11:

score: -100
Wrong Answer
time: 89ms
memory: 9896kb

input:

10 300000
2 80591 44947 481 327
2 75950 2449 866 938
2 99608 77677 797 190
2 58139 15935 651 10
2 44816 33174 358 436
2 38004 26636 226 565
2 469 38698 415 136
2 42979 87602 981 867
2 60596 22147 89 853
2 48278 17909 953 392
692991526086 159941543361 696799547314 839250682232 929834822694 5575324243...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

wrong answer 50013th numbers differ - expected: '0.0000000', found: '6071653.2232112', error = '6071653.2232112'