QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#638177#8037. Gambler's RuinlonelywolfAC ✓452ms50184kbC++202.1kb2024-10-13 15:07:212024-10-13 15:07:24

Judging History

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

  • [2024-10-13 15:07:24]
  • 评测
  • 测评结果:AC
  • 用时:452ms
  • 内存:50184kb
  • [2024-10-13 15:07:21]
  • 提交

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<double> p(n + 1);
 	vector<int> 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<double> a(1, -1);
 	vector<int> b(1);
 	for (int i = 1; i <= n; i++) {
 		if (cmp(p[ord[i]], a.back()) == 0) {
 			b[b.size() - 1] += c[ord[i]];
 		} else {
 			a.push_back(p[ord[i]]);
 			b.push_back(c[ord[i]]);
 		}
 	}

 	n = a.size() - 1;

 	// for (int i = 1; i <= n; i++) {
 	// 	cout << a[i] << " \n"[i == n];
 	// }
 	// for (int i = 1; i <= n; i++) {
 	// 	cout << b[i] << " \n"[i == n];
 	// }
 	
 	vector<int> pre(n + 1), suf(n + 2);
 	for (int i = 1; i <= n; i++) {
 		pre[i] = pre[i - 1] + b[i];
 	}
 	for (int i = n; i >= 1; i--) {
 		suf[i] = suf[i + 1] + b[i];
 	}

 	double ans = 0;

 	for (int i = 0; i <= n; i++) {
 		if (cmp(a[i], 0) == 0) {
 			break;
 		}
 		double x = i == 0 ? 0 : 1.0 / a[i];
 		double sx = pre[i];

	 	auto calc = [&](int b) {
	 		int pos = n + 1 - b;
	 		if (cmp(a[pos], 1) == 0) {
	 			return -1e18;
	 		}
	 		// cout << pos << "\n";
	 		double y = b == 0 ? 0 : 1.0 / (1 - a[pos]);
			double sy = suf[pos];
			// cout << x << " " << y << " " << sx << " " << sy << " " << sx + sy - max(sx * x, sy * y) << "\n";
			return sx + sy - max(sx * x, sy * y);
	 	};
 		int l = 0, r = n - i;
 		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 j = l; j <= r; j++) {
 			ans = max(ans, calc(j));
 		}
 	}

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

    return 0;
}  
  

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

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

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

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

input:

1
0 1

output:

0.0000000000

result:

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

Test #4:

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

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

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

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

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

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

input:

2
0 100000
0.000001 1

output:

0.0000000000

result:

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

Test #10:

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

input:

2
0 1000000000
0.000001 1

output:

1.0000000000

result:

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

Test #11:

score: 0
Accepted
time: 443ms
memory: 49432kb

input:

1000000
0.375733 595197307
0.505261 377150668
0.517039 15795246
0.448099 228176467
0.529380 871983979
0.905546 876268308
0.095891 272104456
0.500302 916153337
0.128705 355768079
0.070600 78747362
0.444107 466118868
0.194987 298494965
0.462293 593292779
0.287909 838058266
0.237226 934603199
0.391909 ...

output:

85718080941203.0625000000

result:

ok found '85718080941203.0625000', expected '85718080941203.0156250', error '0.0000000'

Test #12:

score: 0
Accepted
time: 294ms
memory: 26876kb

input:

1000000
0.353000 999523129
0.526000 14560746
0.978000 319977952
0.324000 353889639
0.535500 497827437
0.153000 660990580
0.482000 391332319
0.050000 118814686
0.862500 774878817
0.417500 124874110
0.172500 789760737
0.058000 236910286
0.596000 585483625
0.176500 388072811
0.838000 806903092
0.613000...

output:

86000987369343.9062500000

result:

ok found '86000987369343.9062500', expected '86000987369343.9218750', error '0.0000000'

Test #13:

score: 0
Accepted
time: 272ms
memory: 26692kb

input:

1000000
0.200000 715833054
0.250000 346181893
0.700000 84047805
0.225000 911121283
0.575000 349964342
0.200000 472178743
0.400000 487500419
0.775000 358482180
0.525000 282051084
0.475000 664059239
0.350000 143371889
0.075000 768191797
0.025000 892648527
0.250000 266570522
0.175000 590192616
0.775000...

output:

90690663939242.5312500000

result:

ok found '90690663939242.5312500', expected '90690663939242.5468750', error '0.0000000'

Test #14:

score: 0
Accepted
time: 452ms
memory: 47776kb

input:

1000000
0.483249 58806278
0.092943 43698395
0.682093 234500498
0.899881 212323106
0.031970 94677621
0.248163 61052399
0.577708 189447689
0.737973 129234039
0.210538 112081344
0.451271 24559811
0.411130 846942
0.916990 268662655
0.992736 184750465
0.112959 105654084
0.932484 8474182
0.949654 21518817...

output:

16307385621417.6093750000

result:

ok found '16307385621417.6093750', expected '16307385621417.6074219', error '0.0000000'

Test #15:

score: 0
Accepted
time: 445ms
memory: 50184kb

input:

1000000
0.019963 244843587
0.361281 50413366
0.776551 132525209
0.435213 112540619
0.689322 261233354
0.023354 75471114
0.897100 120761316
0.650546 203049584
0.562689 213573846
0.606257 117745257
0.242362 401834266
0.331500 571471418
0.172223 291092482
0.713109 169535508
0.056464 106853676
0.068823 ...

output:

38012397725371.2031250000

result:

ok found '38012397725371.2031250', expected '38012397725371.1953125', error '0.0000000'

Test #16:

score: 0
Accepted
time: 317ms
memory: 27588kb

input:

1000000
0.299950 14454994
0.590800 131103748
0.168700 31811722
0.640950 153861933
0.097300 42347624
0.689900 25513183
0.313950 7694955
0.434400 41038786
0.992950 549929012
0.844350 177512169
0.193800 85807309
0.930300 78556126
0.920950 132277934
0.786750 282121687
0.420200 110220790
0.541000 9878024...

output:

18011656371809.6718750000

result:

ok found '18011656371809.6718750', expected '18011656371809.6757812', error '0.0000000'

Test #17:

score: 0
Accepted
time: 441ms
memory: 48488kb

input:

1000000
0.319563 16045815
0.898271 42370223
0.026295 36626864
0.009444 366071738
0.204970 43180228
0.686325 9473412
0.027009 25042313
0.659717 39445987
0.258480 45282965
0.472879 23682796
0.282075 8710935
0.512861 44842140
0.884086 10841294
0.600897 35981067
0.849081 41822205
0.643385 44337405
0.898...

output:

5561235835638.1347656250

result:

ok found '5561235835638.1347656', expected '5561235835638.1347656', error '0.0000000'

Test #18:

score: 0
Accepted
time: 319ms
memory: 30452kb

input:

1000000
0.253950 46
0.559560 542
0.009900 32083
0.403350 413
0.263990 425
0.921800 698
0.783520 455
0.530070 967
0.213120 478
0.050290 874
0.080430 599
0.992630 64
0.820820 475
0.595230 539
0.592450 290
0.393920 657
0.829040 339
0.831190 655
0.634960 910
0.991650 788
0.171040 707
0.599630 505
0.9605...

output:

1639467837.6792602539

result:

ok found '1639467837.6792603', expected '1639467837.6792715', error '0.0000000'

Test #19:

score: 0
Accepted
time: 440ms
memory: 49060kb

input:

1000000
0.898172 7258266
0.104763 240434786
0.719320 63025017
0.422009 267258882
0.358730 246736331
0.183381 333433297
0.156389 498175665
0.797353 4106581
0.176858 677562755
0.519227 23114268
0.813408 17408292
0.661235 68857040
0.579091 35432878
0.451862 60091054
0.851985 8763380
0.508252 72544830
0...

output:

20717770537103.9218750000

result:

ok found '20717770537103.9218750', expected '20717770537103.9140625', error '0.0000000'

Test #20:

score: 0
Accepted
time: 441ms
memory: 47672kb

input:

1000000
0.506643 11838878
0.022718 7
0.215186 49647
0.189161 41240
0.601065 47155106
0.617912 38963493
0.924862 187751265
0.570828 34596465
0.296104 606617
0.819090 181192827
0.541691 22738007
0.978440 701932225
0.678464 39014036
0.879408 0
0.289540 589194
0.360810 1544441
0.335420 142408
0.749706 1...

output:

6131806884974.7578125000

result:

ok found '6131806884974.7578125', expected '6131806884974.7607422', error '0.0000000'

Test #21:

score: 0
Accepted
time: 358ms
memory: 40436kb

input:

1000000
0.268276 9
0.483196 7
0.131214 2
0.937202 2
0.227950 2
0.707708 1
0.776346 7
0.031180 4
0.651482 10
0.359102 9
0.455016 9
0.302518 2
0.270340 7
0.500180 2
0.602974 2
0.409752 5
0.949974 8
0.425086 3
0.978080 0
0.764962 5
0.793300 5
0.802016 6
0.871474 3
0.007990 5
0.681198 4
0.040534 2
0.667...

output:

4981943.0000000000

result:

ok found '4981943.0000000', expected '4981943.0000000', error '0.0000000'

Test #22:

score: 0
Accepted
time: 401ms
memory: 40456kb

input:

1000000
0.119382 617256
0.363456 4259814
0.241892 8125466
0.349642 1231977
0.178516 3859513
0.839628 6794539
0.787806 9774871
0.069012 3739020
0.959006 9910122
0.036676 6096603
0.016698 1864421
0.309786 3306756
0.695128 7551944
0.874058 406134
0.196980 8336449
0.277616 5104388
0.292342 6722343
0.392...

output:

861363030857.9038085938

result:

ok found '861363030857.9038086', expected '861363030857.9036865', error '0.0000000'

Test #23:

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

input:

1000
0.409000 51
0.119000 84
0.191000 34
0.686000 95
0.348000 1
0.308000 47
0.355000 85
0.896000 7
0.310000 52
0.053000 28
0.542000 5
0.621000 58
0.583000 16
0.856000 61
0.145000 88
0.628000 85
0.647000 38
0.951000 77
0.285000 96
0.889000 28
0.168000 59
0.053000 33
0.848000 16
0.195000 57
0.142000 3...

output:

8781.9645390071

result:

ok found '8781.9645390', expected '8781.9645390', error '0.0000000'

Extra Test:

score: 0
Extra Test Passed