UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#199412#281. 分配UperFicial1003852ms33468kbC++1.8kb2023-12-16 07:53:452023-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