QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#33198#958. Lockout vs touristWu_RenWA 705ms69304kbC++17670b2022-05-29 21:05:542022-05-29 21:05:56

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-29 21:05:56]
  • Judged
  • Verdict: WA
  • Time: 705ms
  • Memory: 69304kb
  • [2022-05-29 21:05:54]
  • Submitted

answer

#include <bits/stdc++.h>
typedef long double ld;
using namespace std;
int n,m,c[22];
ld f[4194304],b[22],a[22];
ld calc(){
	ld K=0,B=0;
	for(int i=0;i<m;i++) if(b[i]<a[i]) K+=1/(b[i]-a[i]),B+=-a[i]/(b[i]-a[i]);
	for(int i=0;i<m;i++){
		if(K*a[i]+B<=1) return (1-B)/K;
		if(b[i]<a[i]) K-=1/(b[i]-a[i]),B-=-a[i]/(b[i]-a[i]);
	}
	return (1-B)/K;
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&c[i]);
	sort(c,c+n);
	for(int S=1;S<(1<<n);S++){
		m=0;
		for(int i=0;i<n;i++) if((S>>i)&1){
			b[m]=f[S^(1<<i)],a[m++]=c[i];
			if(b[m-1]>=a[m-1]) f[S]=max(f[S],a[m-1]);
		}
		f[S]=max(f[S],calc());
	}
	printf("%.18Lf",f[(1<<n)-1]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
6 7

output:

3.230769230769230769

result:

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

Test #2:

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

input:

3
1 1 1

output:

0.833333333333333333

result:

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

Test #3:

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

input:

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

output:

9.442271386610331755

result:

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

Test #4:

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

input:

2
1 1000000000

output:

0.999999999000000001

result:

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

Test #5:

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

input:

5
76 57 68 36 63

output:

63.353965112431497513

result:

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

Test #6:

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

input:

10
550060 445055 787034 728427 572554 894096 875473 622886 575460 119034

output:

818911.373928632773584013

result:

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

Test #7:

score: 0
Accepted
time: 3ms
memory: 4256kb

input:

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

output:

9.498679631760098494

result:

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

Test #8:

score: 0
Accepted
time: 150ms
memory: 20548kb

input:

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

output:

2.999975198412698412

result:

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

Test #9:

score: 0
Accepted
time: 337ms
memory: 36528kb

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.282169205544050783

result:

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

Test #10:

score: 0
Accepted
time: 705ms
memory: 69304kb

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.348148638673592359

result:

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

Test #11:

score: 0
Accepted
time: 687ms
memory: 69296kb

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.534057118986140722

result:

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

Test #12:

score: 0
Accepted
time: 684ms
memory: 69296kb

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.442125287786154786

result:

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

Test #13:

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

input:

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

output:

999999724.426807760144583881

result:

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

Test #14:

score: -100
Wrong Answer
time: 522ms
memory: 69284kb

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:

994055435.082251081999856979

result:

wrong answer 1st numbers differ - expected: '1000000000.0000000', found: '994055435.0822511', error = '0.0059446'