ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#199412 | #281. 分配 | UperFicial | 100 | 3852ms | 33468kb | C++ | 1.8kb | 2023-12-16 07:53:45 | 2023-12-16 12:38:31 |
answer
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const long double eps=1e-9;
int n;
bool vis[N];
long double V,M,len,ans;
struct mat
{
double v,m,h;
int id;
}s[N];
bool cmp(mat a,mat b){return a.h<b.h;}
bool check(double mid)
{
int id=1;ans=0;//cout<<mid<<" ";
while(s[id].v<mid)
{
mid-=s[id].v;
id++;
}
ans+=(s[id].v-mid)*s[id].h;
mid=len-(s[id].v-mid);
if(mid<0)ans=s[id].h*len;
else
{
id++;
while(s[id].v<mid&&id<=n)
{
mid-=s[id].v;
ans+=s[id].m;
id++;
}
ans+=mid*s[id].h;
}
if(ans>=M/2-eps)return 1;
return 0;
}
signed main()
{
// freopen("bread.in","r",stdin);
// freopen("bread.out","w",stdout);
n=read();V=0;M=0;ans=0;
for(int i=1;i<=n;i++)
{
s[i].v=read(),s[i].id=i,V+=s[i].v,vis[i]=0;
s[i].m=read(),s[i].h=s[i].m/s[i].v,M+=s[i].m;
}
sort(s+1,s+1+n,cmp);
len=V/2;
double l=0,r=len,mid;
for(int i=1;i<=250;i++)
{
mid=(l+r)/2;
if(check(mid))r=mid;
else l=mid;
}
vis[n+1]=vis[n+2]=1;
int id=1;
while(s[id].v<mid)
{
mid-=s[id].v;
id++;
}
ans+=(s[id].v-mid)*s[id].h;
cout<<"2\n";
printf("%d %.14f\n",s[id].id,mid/s[id].v);
double p=len/(s[id].v-mid);
mid=len-(s[id].v-mid);
if(mid<0)
{
vis[n+2]=0;
printf("%d %.14f\n",n+1,p);
}
else
{
id++;
while(s[id].v<mid&&id<=n)
{
mid-=s[id].v;
ans+=s[id].m;
vis[s[id].id]=1;
id++;
}
ans+=mid*s[id].m;
printf("%d %.14f\n",s[id].id,(s[id].v-mid)/s[id].v);
}
int num=0;
for(int i=1;i<=n+2;i++)if(vis[i])num++;
cout<<num<<"\n";
for(int i=1;i<=n+2;i++)if(vis[i])cout<<i<<" ";cout<<"\n";
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 0ms
memory: 1240kb
input:
1 233 2333
output:
2 1 0.00000000000000 2 0.50000000000000 1 2
result:
ok Accepted
Test #2:
score: 0
Accepted
time: 0ms
memory: 1252kb
input:
193 4354627 4863875 4858430 2330743 1008460 5169725 3756139 8767910 933558 572457 7043707 7351736 31...
output:
2 143 0.23136309100964 100 0.12527891383159 84 1 5 6 13 14 18 20 25 26 27 28 32 34 35 36 37 43 46 47...
result:
ok Accepted
Test #3:
score: 0
Accepted
time: 0ms
memory: 1252kb
input:
191 4 16 11 8 29 711 78 7 50 9 117 11 10 74 16 3 13 614 2 37 7 20 6 17 126 14 13 6 125 40 454 22 25 ...
output:
2 111 0.11388140161591 179 0.98899371071063 141 1 2 4 5 6 8 11 12 13 14 15 17 18 19 20 21 23 24 26 2...
result:
ok Accepted
Test #4:
score: 0
Accepted
time: 0ms
memory: 1252kb
input:
196 25 19 24 18 26 21 12 29 58 8 3 18 252 15 14 2 24 19 6 12 64 17 13 50 10 28 15 14 23 19 12 17 14 ...
output:
2 28 0.95928518488006 100 0.47714321011329 143 1 2 3 5 7 8 9 10 11 14 15 16 17 19 20 21 22 26 27 29 ...
result:
ok Accepted
Test #5:
score: 0
Accepted
time: 0ms
memory: 1252kb
input:
195 1080 2918 1781 2134 2622 2401 1568 780 2762 31 791 397 722 2265 2758 2978 371 744 1115 2453 926 ...
output:
2 169 0.81064762034065 154 0.07228323606519 83 2 3 8 11 12 13 15 22 24 27 31 32 43 45 49 53 55 57 59...
result:
ok Accepted
Test #6:
score: 0
Accepted
time: 0ms
memory: 1240kb
input:
197 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 18 ...
output:
2 172 0.99999999870103 197 0.49979855555556 2 198 199
result:
ok Accepted
Subtask #2:
score: 20
Accepted
Test #7:
score: 20
Accepted
time: 0ms
memory: 1312kb
input:
1997 2275331 1900470 1144526 4929433 6934463 8204992 5935709 5402053 6003272 3696849 8791051 7800100...
output:
2 1975 0.31410168106035 759 0.91399558773184 832 1 3 4 5 6 7 10 13 14 16 17 18 19 20 21 24 25 26 27 ...
result:
ok Accepted
Test #8:
score: 0
Accepted
time: 0ms
memory: 1312kb
input:
1995 29 30 139 32 6 28 17 5 27 27 11 69 16 187 8 49 29 29 93 18 20 31 4 11 60 50 128 2 1 25 331 52 5...
output:
2 222 0.68494734753364 1246 0.24380931527972 1886 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 18 19 20 21...
result:
ok Accepted
Test #9:
score: 0
Accepted
time: 0ms
memory: 1312kb
input:
1992 21 29 29 14 5 24 25 27 10 31 26 27 57 64 4 6 14 4 7 26 7 26 13 20 28 21 10 3 7 8 7 8 21 5 3 111...
output:
2 470 0.25195421551399 189 0.72878280291981 1082 1 2 4 6 7 8 12 13 15 16 19 20 21 22 24 25 26 28 29 ...
result:
ok Accepted
Test #10:
score: 0
Accepted
time: 2ms
memory: 1312kb
input:
1992 2266 1359 2739 1508 2427 2868 1294 2892 778 2102 2519 137 905 1345 1051 1026 2054 2671 645 623 ...
output:
2 696 0.48804175227956 1327 0.13953452184411 832 3 7 8 9 10 11 12 14 15 18 20 22 23 27 28 32 36 41 4...
result:
ok Accepted
Test #11:
score: 0
Accepted
time: 0ms
memory: 1304kb
input:
1991 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 18...
output:
2 612 0.99999999870105 1991 0.49795472222222 2 1992 1993
result:
ok Accepted
Subtask #3:
score: 20
Accepted
Test #12:
score: 20
Accepted
time: 60ms
memory: 4472kb
input:
99995 4569847 3390637 7841079 3609618 1846535 4721392 2987498 7765317 8348524 8155158 480615 8453425...
output:
2 49458 0.30718823993426 45159 0.06371846801077 41896 1 5 10 14 17 23 24 28 32 33 35 36 38 43 48 51 ...
result:
ok Accepted
Test #13:
score: 0
Accepted
time: 67ms
memory: 4476kb
input:
99994 8 26 62 51 26 11 3 6 357 32 9 756 23 126 12 73 4 14 56 15 15 106 69 6 22 21 26 1926 13 44 17 3...
output:
2 38269 0.92953200859873 7081 0.87467017789420 99827 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19...
result:
ok Accepted
Test #14:
score: 0
Accepted
time: 47ms
memory: 4472kb
input:
99991 22 12 28 5 22 59 11 7 29 19 24 389 19 59 9 26 10 98 19 32 21 19 28 29 3 16 177 5 105 19 14 20 ...
output:
2 78252 0.98623853209226 30257 0.16513761471618 55338 1 4 5 10 11 12 16 17 19 20 22 27 28 30 32 33 3...
result:
ok Accepted
Test #15:
score: 0
Accepted
time: 52ms
memory: 4476kb
input:
100000 139 2301 1141 908 1114 1859 803 2389 832 1240 307 403 1343 1439 1791 2596 859 2083 867 52 207...
output:
2 9694 0.95557073772932 22882 0.71320650602779 46743 2 3 5 6 7 8 11 13 21 27 30 31 34 35 36 38 40 41...
result:
ok Accepted
Test #16:
score: 0
Accepted
time: 27ms
memory: 4460kb
input:
99995 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 1...
output:
2 30550 0.99999999879908 99995 0.39722838888889 2 99996 99997
result:
ok Accepted
Subtask #4:
score: 40
Accepted
Test #17:
score: 40
Accepted
time: 758ms
memory: 33468kb
input:
999993 3588778 7921136 2915626 3096636 589691 2088724 1675751 6307271 8698122 5082393 4789144 616363...
output:
2 225306 0.91776708160728 528543 0.91639194321245 418676 2 5 6 7 8 9 10 11 12 15 17 19 23 25 30 32 3...
result:
ok Accepted
Test #18:
score: 0
Accepted
time: 948ms
memory: 33464kb
input:
999997 128 31 126 6 25 10 17 1 27 839 28 67 14 209 32 10 28 9 26 25 3 57 47 17 18 64 18 35 15 32 23 ...
output:
2 694292 0.78481797489236 860797 0.27891150195348 994260 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1...
result:
ok Accepted
Test #19:
score: 0
Accepted
time: 676ms
memory: 33464kb
input:
999992 5 23 19 16 19 21 42 16 13 2 20 25 31 20 32 24 30 32 18 8 7 18 98 4 23 8 15 10 41 6 30 26 74 3...
output:
2 419727 0.04278462648738 192577 0.74401740406950 553536 2 3 6 7 8 9 10 14 16 17 19 22 23 24 28 30 3...
result:
ok Accepted
Test #20:
score: 0
Accepted
time: 764ms
memory: 33468kb
input:
1000000 1466 2152 876 2606 2621 609 2601 2715 2356 335 1310 2278 742 880 25 264 2139 798 2237 2333 1...
output:
2 361614 0.96464315165761 441811 0.59348894550172 462327 1 4 6 7 10 17 22 25 30 33 35 36 37 38 42 43...
result:
ok Accepted
Test #21:
score: 0
Accepted
time: 451ms
memory: 33456kb
input:
999989 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 18 18 19 19 ...
output:
2 959104 0.62162162138051 959111 0.62162162187613 256753 39063 39064 39065 39066 39067 39068 39069 3...
result:
ok Accepted
Extra Test:
score: 0
Extra Test Passed