QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#139516#5505. Great Chaseammardab3an#WA 355ms3784kbC++171.0kb2023-08-13 19:43:142023-08-13 19:43:16

Judging History

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

  • [2023-08-13 19:43:16]
  • 评测
  • 测评结果:WA
  • 用时:355ms
  • 内存:3784kb
  • [2023-08-13 19:43:14]
  • 提交

answer

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const ll N = 1e6 + 10, MM = 1e9 + 7, MAX = 1e18;


int solve() {
	int n; cin >> n;
	ll v; cin >> v;
	vector<pair<ll, ll>>lef, rig;
	for (int i = 0; i < n; i++) {
		ll a, b; cin >> a >> b;
		if (a < 0) {
			lef.emplace_back(a, b);
		}
		else {
			rig.emplace_back(a, b);
		}
	}

	double l = 0, r = 1e18;
	double time = 0;
	int num = 100;
	while (abs(r - l) > 1e-9&&num) {
		double mid = l + (r - l) / 2.0;
		double mxlef = -MAX, mnrig = MAX;
		for (auto x : lef) {
			mxlef = max(mxlef, mid * x.second + x.first);
		}
		for (auto x : rig) {
			mnrig = min(mnrig, x.first - mid * x.second);
		}
		if (mnrig <= mxlef) {
			time = mid;
			r = mid;
		}
		else {
			l = mid;
		}
		num--;
	}
	printf("%.10f\n", time * v);
	return 0;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	cin >> t;
	int i = 1;
	while (t--) {
		//cout << "case " << i << ": ";
		solve();
	}
	return 0;
}
/*
204

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
4 9
10 2
-7 2
-6 1
7 1
2 8
-1 7
1 6
2 3
-1000000000000 1
1000000000000 1

output:

38.2500000003
1.2307692325
3000000000000.0000000000

result:

ok 3 numbers

Test #2:

score: -100
Wrong Answer
time: 355ms
memory: 3784kb

input:

10000
200 997007
405524182320 754760
686939601648 419804
687047488212 715566
1446157132 4594
-670522037 4673
763634629282 253755
424307411732 275041
1582708381 8473
-667425982 4622
-522841486 1427
702430907988 460271
1405423646 1060
1497754648 6227
883363410675 723547
56899800372 46435
-810216390 64...

output:

145405766328.3494873047
16414958969.7277622223
5202715639.8355846405
321977234.1563583016
45384199210.2218246460
183885744.7692473531
1708925225.2309525013
89786664971.5586242676
13924365606.2879676819
412975327.5556929708
965508404.5124481916
4703493416.2883796692
352961619.3818355799
5575125771.79...

result:

wrong answer 4566th numbers differ - expected: '1.0000010', found: '1.0000484', error = '0.0000474'