QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#51324#958. Lockout vs touristtricyzhkxAC ✓1316ms36696kbC++141.0kb2022-10-01 20:15:522022-10-01 20:15:56

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-01 20:15:56]
  • 评测
  • 测评结果:AC
  • 用时:1316ms
  • 内存:36696kb
  • [2022-10-01 20:15:52]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
int id[30];
double f[5000000],a[30],b[30];
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++) scanf("%lf",&a[i]);
	for(int i=1;i<(1<<n);i++)
	{
		vector<int> legal;
		for(int j=0;j<n;j++)
			if((i>>j)&1) legal.push_back(j);
		double mx=0;
		for(int j:legal) b[j]=f[i^(1<<j)],mx=max(mx,min(a[j],b[j]));
		double K=0,B=0;
		int cnt=0;
		for(int j:legal)
			if(a[j]>b[j]) id[++cnt]=j;
		sort(id+1,id+cnt+1,[](int i,int j){return a[i]>a[j];});
		id[cnt+1]=n;
		for(int j=1;j<=cnt;j++)
		{
			K+=1/(a[id[j]]-b[id[j]]);B+=a[id[j]]/(a[id[j]]-b[id[j]]);
			double x=(B-1)/K;
			if(x>=a[id[j+1]]){mx=max(mx,x);break;}
		}
		K=B=0;cnt=0;
		for(int j:legal)
			if(a[j]<b[j]) id[++cnt]=j,B+=1;
		sort(id+1,id+cnt+1,[](int i,int j){return b[i]>b[j];});
		id[cnt+1]=n;
		for(int j=1;j<=cnt;j++)
		{
			K+=1/(b[id[j]]-a[id[j]]);B-=1+a[id[j]]/(b[id[j]]-a[id[j]]);
			double x=(1-B)/K;
			if(x>=b[id[j+1]]){mx=max(mx,x);break;}
		}
		f[i]=mx;
	}
	printf("%.10lf\n",f[(1<<n)-1]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3676kb

input:

2
6 7

output:

3.2307692308

result:

ok found '3.2307692', expected '3.2307692', error '0.0000000'

Test #2:

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

input:

3
1 1 1

output:

0.8333333333

result:

ok found '0.8333333', expected '0.8333333', error '0.0000000'

Test #3:

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

input:

11
1 2 3 4 5 6 7 8 9 10 11

output:

9.4422713866

result:

ok found '9.4422714', expected '9.4422714', error '0.0000000'

Test #4:

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

input:

2
1 1000000000

output:

0.9999999990

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #5:

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

input:

5
76 57 68 36 63

output:

63.3539651124

result:

ok found '63.3539651', expected '63.3539651', error '0.0000000'

Test #6:

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

input:

10
550060 445055 787034 728427 572554 894096 875473 622886 575460 119034

output:

818911.3739286327

result:

ok found '818911.3739286', expected '818911.3739286', error '0.0000000'

Test #7:

score: 0
Accepted
time: 10ms
memory: 4060kb

input:

15
10 8 9 6 9 5 3 9 7 8 7 6 7 10 7

output:

9.4986796318

result:

ok found '9.4986796', expected '9.4986796', error '0.0000000'

Test #8:

score: 0
Accepted
time: 283ms
memory: 11936kb

input:

20
3 2 2 1 2 3 1 3 3 2 1 2 3 2 3 2 3 1 3 1

output:

2.9999751984

result:

ok found '2.9999752', expected '2.9999752', error '0.0000000'

Test #9:

score: 0
Accepted
time: 602ms
memory: 20180kb

input:

21
608646711 538679781 175667175 596079164 43084965 174585378 46825084 647100103 820432909 254925688 469580725 888475497 802835182 554123188 53822453 849477025 715668397 194908968 407987651 349577139 457598738

output:

831669480.2821693420

result:

ok found '831669480.2821693', expected '831669480.2821692', error '0.0000000'

Test #10:

score: 0
Accepted
time: 1305ms
memory: 36696kb

input:

22
593316975 268451765 664075355 817013319 325389147 553878522 663160635 289932897 995002446 771863307 252061346 171723220 102306933 722521207 52895206 996540774 335816175 415049181 629862034 371890996 327908946 357122932

output:

899795716.3481487036

result:

ok found '899795716.3481487', expected '899795716.3481486', error '0.0000000'

Test #11:

score: 0
Accepted
time: 1089ms
memory: 36576kb

input:

22
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152

output:

895851.5340571189

result:

ok found '895851.5340571', expected '895851.5340571', error '0.0000000'

Test #12:

score: 0
Accepted
time: 1077ms
memory: 36512kb

input:

22
1000001 1000002 1000003 1000004 1000005 1000006 1000007 1000008 1000009 1000010 1000011 1000012 1000013 1000014 1000015 1000016 1000017 1000018 1000019 1000020 1000021 1000022

output:

1000020.4421252878

result:

ok found '1000020.4421253', expected '1000020.4421253', error '0.0000000'

Test #13:

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

input:

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

output:

999999724.4268072844

result:

ok found '999999724.4268073', expected '999999724.4268078', error '0.0000000'

Test #14:

score: 0
Accepted
time: 1064ms
memory: 36452kb

input:

22
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

output:

1000000000.0000000000

result:

ok found '1000000000.0000000', expected '1000000000.0000000', error '0.0000000'

Test #15:

score: 0
Accepted
time: 618ms
memory: 20064kb

input:

21
728645832 499372030 251249515 630474794 602042850 686098859 164334367 88772048 746898743 759695983 264178590 77784010 969248695 194487863 333341710 979132664 389787588 237190234 881432878 265149252 412117176

output:

904983051.3139024973

result:

ok found '904983051.3139025', expected '904983051.3139025', error '0.0000000'

Test #16:

score: 0
Accepted
time: 1316ms
memory: 36628kb

input:

22
314176712 731128902 493616429 895194945 944147610 264333375 726725941 275896968 22590087 347618504 348534546 434375739 41042380 833655175 812796321 965972943 895005482 106474689 268333939 73317639 692105187 921714965

output:

931516498.4413915873

result:

ok found '931516498.4413916', expected '931516498.4413917', error '0.0000000'

Test #17:

score: 0
Accepted
time: 1184ms
memory: 36680kb

input:

22
619182033 404890231 483695686 505942949 17974691 191865554 285191465 20725875 768798333 549358594 794203186 500489670 673327262 914017660 189568084 691193705 497008772 813277003 87684441 894142475 811860050 857365145

output:

872232180.5260175467

result:

ok found '872232180.5260175', expected '872232180.5260175', error '0.0000000'

Test #18:

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

input:

1
1

output:

0.0000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'