QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#488411 | #4568. Budget Distribution | arnold518 | WA | 86ms | 9808kb | C++17 | 2.9kb | 2024-07-24 01:38:29 | 2024-07-24 01:38:29 |
Judging History
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-7;
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);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5112kb
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: 0ms
memory: 5008kb
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: 6420kb
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: 6084kb
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: 1ms
memory: 5056kb
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: 0ms
memory: 5060kb
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: 5272kb
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: 5284kb
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: 0ms
memory: 6572kb
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: 2ms
memory: 6776kb
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: 86ms
memory: 9808kb
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'