QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#352013#958. Lockout vs touristchenxinyang2006WA 1ms3904kbC++141.9kb2024-03-12 19:24:052024-03-12 19:24:05

Judging History

This is the latest submission verdict.

  • [2024-03-12 19:24:05]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3904kb
  • [2024-03-12 19:24:05]
  • Submitted

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(){
	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;
		dp[S] = inf;
		if(nxt[n - 1] == -1) dp[S] = 0;
//		rep(i,0,n - 1) printf("%d ",nxt[i]);
//		printf("\n");
		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(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: 3900kb

input:

2
6 7

output:

3.2307692308

result:

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

Test #2:

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

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: 0ms
memory: 3904kb

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: 3840kb

input:

2
1 1000000000

output:

0.9999999990

result:

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

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3836kb

input:

5
76 57 68 36 63

output:

62.8161435690

result:

wrong answer 1st numbers differ - expected: '63.3539651', found: '62.8161436', error = '0.0084892'