QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#352022 | #958. Lockout vs tourist | chenxinyang2006 | AC ✓ | 669ms | 36700kb | C++14 | 2.1kb | 2024-03-12 19:36:44 | 2024-03-12 19:36:45 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;
template <class T>
void chkmax(T &x,T y){
if(x < y) x = y;
}
template <class T>
void chkmin(T &x,T y){
if(x > y) x = y;
}
inline int popcnt(int x){
return __builtin_popcount(x);
}
inline int ctz(int x){
return __builtin_ctz(x);
}
/*ll power(ll p,int k = mod - 2){
ll ans = 1;
while(k){
if(k % 2 == 1) ans = ans * p % mod;
p = p * p % mod;
k /= 2;
}
return ans;
}*/
int n;
int a[25];
db b[25];
int nxt[25];
#define eps 1e-7
db dp[1 << 22];
int main(){
// freopen("test.in","r",stdin);
scanf("%d",&n);
rep(i,0,n - 1) scanf("%d",&a[i]);
sort(a,a + n);
rep(S,0,(1 << n) - 1){
int j = -1;
rep(i,0,n - 1){
if(((S >> i) & 1) == 0){
nxt[i] = j;
continue;
}
b[i] = dp[S - (1 << i)];
if(b[i] < a[i] - eps) j = i;
nxt[i] = j;
}
db sum0 = -1,sum1 = 0;
if(nxt[n - 1] == -1) dp[S] = 0;
else dp[S] = a[nxt[n - 1]];
// rep(i,0,n - 1) printf("%d ",nxt[i]);
// printf("\n");
// if(S + 1 == (1 << n)){
// printf("qwq\n");
// rep(i,0,n - 1) printf("%.5f %.5f\n",a[i] * 1.0,b[i]);
// }
per(i,n - 1,0){
if(((S >> i) & 1) == 0 || b[i] >= a[i] - eps) continue;
sum0 += a[i] / (a[i] - b[i]);
sum1 += 1 / (a[i] - b[i]);
if(sum0 > a[i] * sum1) continue;
if(i && nxt[i - 1] != -1) chkmin(dp[S],max(a[nxt[i - 1]] * 1.0,sum0 / sum1));
else chkmin(dp[S],sum0 / sum1);
// printf("sum0=%.10f sum1=%.10f\n",sum0,sum1);
}
rep(i,0,n - 1) if((S >> i) & 1 && b[i] >= a[i] - eps) chkmax(dp[S],a[i] * 1.0);
// printf("%d->%.10f\n",S,dp[S]);
}
printf("%.10f\n",dp[(1 << n) - 1]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3868kb
input:
2 6 7
output:
3.2307692308
result:
ok found '3.2307692', expected '3.2307692', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3908kb
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: 1ms
memory: 3908kb
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: 0ms
memory: 3932kb
input:
2 1 1000000000
output:
0.9999999990
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3920kb
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: 1ms
memory: 3900kb
input:
10 550060 445055 787034 728427 572554 894096 875473 622886 575460 119034
output:
818911.3739286328
result:
ok found '818911.3739286', expected '818911.3739286', error '0.0000000'
Test #7:
score: 0
Accepted
time: 4ms
memory: 4128kb
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: 125ms
memory: 12088kb
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: 281ms
memory: 20216kb
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: 602ms
memory: 36700kb
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: 601ms
memory: 36632kb
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: 669ms
memory: 36580kb
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: 3872kb
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: 618ms
memory: 36680kb
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: 281ms
memory: 20244kb
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: 592ms
memory: 36668kb
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: 594ms
memory: 36660kb
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: 3924kb
input:
1 1
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'