QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#628993#8037. Gambler's RuinlonelywolfWA 1ms4032kbC++201.7kb2024-10-10 23:51:592024-10-10 23:52:03

Judging History

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

  • [2024-10-10 23:52:03]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4032kb
  • [2024-10-10 23:51:59]
  • 提交

answer

#include <bits/stdc++.h>  
using namespace std;  

#define int long long  

using db = double;

constexpr db eps = 1e-9;

int sgn(db x) {
	if (x > eps) {
		return 1;
	} else if (x < -eps) {
		return -1;
	}
	return 0;	
}

int cmp(db x, db y) {
	return sgn(x - y);
}

signed main() {  
    ios::sync_with_stdio(false);
    cin.tie(nullptr);  

	int n;
	cin >> n;

	vector<db> p_(n + 1), c_(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> p_[i] >> c_[i];
	}

	vector<int> ord(n + 1);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin() + 1, ord.end(), [&](int i, int j) {
		return p_[i] > p_[j];
	});

	vector<db> p(1, -1);
	vector<int>	c(1);
	int s1 = 0, s2 = 0;
	for (int i = 1; i <= n; i++) {
		if (cmp(p_[ord[i]], 0) == 0) {
			s1 += c_[ord[i]];
		} else if (cmp(p_[ord[i]], 1) == 0) {
			s2 += c_[ord[i]];
		} else if (cmp(p.back(), p_[ord[i]]) == 0) {
			c[c.size() - 1] += c_[ord[i]];
		} else {
			p.push_back(p_[ord[i]]);
			c.push_back(c_[ord[i]]);
		}
	}

	vector<int> suf(n + 2);
	for (int i = n; i >= 1; i--) {
		suf[i] = suf[i + 1] + c[i];
	}

	n = p.size() - 1;
	int sx = s2;
	db ans = min(s1, s2);
	for (int i = 1; i <= n; i++) {
		assert(sgn(p[i]) == 1);
		db x = 1.0 / p[i];
		sx += c[i];
		
		auto calc = [&](int m) {
			assert(sgn(1 - p[m]) == 1);
			db y = 1.0 / (1 - p[m]);
			db sy = s1 + suf[m];
			return 1.0 * sx + 1.0 * sy - max(x * sx, y * sy); 
		};

		int l = i + 1, r = n;
		while (r - l > 5) {
			int lm = (2 * l + r) / 3, rm = (l + 2 * r) / 3;
			if (calc(lm) < calc(rm)) {
				l = lm;
			} else {
				r = rm;
			}
		}
		for (int t = l; t <= r; t++) {
			ans = max(ans, calc(t));
		}
	}

	cout << fixed << setprecision(10) << ans << "\n";

    return 0;
}  
  

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3972kb

input:

2
1 15
0 10

output:

10.0000000000

result:

ok found '10.0000000', expected '10.0000000', error '0.0000000'

Test #2:

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

input:

3
0.4 100
0.5 100
0.6 100

output:

33.3333333333

result:

ok found '33.3333333', expected '33.3333333', error '0.0000000'

Test #3:

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

input:

1
0 1

output:

0.0000000000

result:

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

Test #4:

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

input:

2
1 0
1 100

output:

0.0000000000

result:

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

Test #5:

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

input:

1
0.5 100

output:

0.0000000000

result:

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

Test #6:

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

input:

3
0.4 100
0.6 100
0.6 100

output:

0.0000000000

result:

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

Test #7:

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

input:

3
0.2 100
0.2 100
0.8 100

output:

50.0000000000

result:

ok found '50.0000000', expected '50.0000000', error '0.0000000'

Test #8:

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

input:

2
0.999999 1000000
0.999998 2

output:

0.9999990000

result:

ok found '0.9999990', expected '0.9999990', error '0.0000000'

Test #9:

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

input:

2
0 100000
0.000001 1

output:

0.0000000000

result:

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

Test #10:

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

input:

2
0 1000000000
0.000001 1

output:

0.0000000000

result:

wrong answer 1st numbers differ - expected: '1.0000000', found: '0.0000000', error = '1.0000000'