QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#196433#7239. TrianglejeffqiAC ✓219ms3868kbC++202.0kb2023-10-01 17:24:032023-10-01 17:24:04

Judging History

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

  • [2023-10-01 17:24:04]
  • 评测
  • 测评结果:AC
  • 用时:219ms
  • 内存:3868kb
  • [2023-10-01 17:24:03]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(v) ((int)v.size())
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define ui unsigned int
#define ull unsigned ll
#define i128 __int128
using namespace std;

namespace qiqi {
	const int V = 1e5+1;
	const i128 inf = 1e36;
	using B = bitset<V>;
	void main() {
		int n,m;
		cin >> n >> m;
		vi a(n);
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		sort(all(a));
		i128 ans = inf;
		auto calc = [&](i128 a,i128 b,i128 c) {
			i128 p = a+b+c;
			a *= 2; b *= 2; c *= 2;
			return p*(p-a)*(p-b)*(p-c);
		};
		for (int i = 0; i+1 < n; i++) {
			{
				int p = upper_bound(all(a),a[i+1]-a[i])-a.begin();
				if (p < i) {
					ans = min(ans,calc(a[p],a[i],a[i+1]));
				}
			}
			if (a[i] == a[i+1]) {
				int p = lower_bound(all(a),a[i]+a[i+1])-a.begin()-1;
				if (p > i+1) {
					ans = min(ans,calc(a[p],a[i],a[i+1]));
				}
			}
		}
		B p,q;
		for (int i = 0; i < n; i++) {
			p.set(a[i]); q.set(m-a[i]);
		}
		for (int i = 1; i <= 2*m; i++) {
			int x;
			if (i < m) {
				x = (p&(q>>(m-i)))._Find_first();
			}
			else {
				x = (p&(q<<(i-m)))._Find_first();
			}
			if (x*2 < i) {
				int y = i-x,z = *(lower_bound(all(a),i)-1);
				if (z > y) {
					ans = min(ans,calc(x,y,z));
				}
			}
		}
		if (ans == inf) {
			cout << -1 << '\n';
			return;
		}
		cout << sqrt((double)ans/16) << '\n';
	}
}

int main() {
//	clock_t st = clock();
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cout << fixed << setprecision(15);

	int T = 1;
	cin >> T;
	while (T--) {
		qiqi::main();
	}

//	cout << (double)(clock()-st)/CLOCKS_PER_SEC;
	return 0;
}

詳細信息

Test #1:

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

input:

4
3 3
1 2 3
4 4
1 2 3 4
3 11
5 7 11
6 11
5 7 8 9 10 11

output:

-1
2.904737509655563
12.968712349342937
12.968712349342937

result:

ok 4 numbers

Test #2:

score: 0
Accepted
time: 2ms
memory: 3676kb

input:

20
5 20
15 20 11 17 18
5 20
12 18 13 20 15
5 20
12 10 14 18 16
5 20
18 16 15 11 14
5 20
18 12 11 20 14
5 20
20 15 10 16 12
5 20
12 10 15 13 17
5 20
18 15 13 20 12
5 20
16 18 20 10 14
5 20
11 15 16 13 18
5 20
11 13 16 14 17
5 20
20 14 11 13 16
5 20
16 11 15 13 18
5 20
11 15 13 20 14
5 20
16 10 13 20 ...

output:

81.259999384691113
74.833147735478832
56.568542494923804
73.484692283495349
56.718052681663885
45.596052460711988
56.995065575889988
74.833147735478832
64.992307237087687
69.628927178292784
67.527772064536535
66.000000000000000
69.628927178292784
66.000000000000000
31.975576617162044
85.451375062078...

result:

ok 20 numbers

Test #3:

score: 0
Accepted
time: 214ms
memory: 3852kb

input:

5000
4 20
11 14 16 17
4 20
13 19 10 15
4 20
19 12 16 14
4 20
11 13 10 15
4 20
17 15 14 18
4 20
14 12 19 15
4 20
13 17 19 11
4 20
16 20 12 18
4 20
20 19 12 16
4 20
14 15 18 17
4 20
16 11 12 15
4 20
10 17 16 19
4 20
17 19 18 13
4 20
11 18 15 20
4 20
19 11 10 16
4 20
18 20 15 11
4 20
17 20 10 15
4 20
1...

output:

75.474747432502213
60.794736614282655
81.332650270355757
53.441556863549550
99.679486355016891
78.926785694084870
69.261731858220230
94.101009558877735
95.503599408608679
99.679486355016891
65.238025721200358
78.226833631433664
105.299572648705464
81.387959797503214
42.426406871192853
81.38795979750...

result:

ok 5000 numbers

Test #4:

score: 0
Accepted
time: 212ms
memory: 3780kb

input:

3333
5 30
8 19 7 14 24
5 30
22 29 9 26 21
5 30
27 16 13 10 29
5 30
14 6 25 28 22
5 30
23 19 13 14 21
5 30
24 9 28 30 5
5 30
20 19 23 5 11
5 30
30 7 25 23 11
5 30
22 24 21 15 26
5 30
26 5 28 12 24
5 30
8 23 7 29 14
5 30
29 13 20 24 11
5 30
27 25 13 18 22
5 30
25 27 23 7 18
5 30
16 20 9 12 7
5 30
24 1...

output:

18.799933510520724
50.697016677512693
64.918699155174082
60.555243373303355
81.240384046359608
38.819292883822598
31.275989192989563
66.813172353960269
150.784614599766115
38.819292883822598
18.799933510520724
66.000000000000000
101.034647522520714
49.477267507411923
31.304951684997057
41.2310562561...

result:

ok 3333 numbers

Test #5:

score: 0
Accepted
time: 219ms
memory: 3728kb

input:

500
6 200
173 127 108 151 145 182
6 200
178 189 113 127 187 158
6 200
141 161 181 111 107 167
6 200
140 137 190 184 153 155
6 200
186 195 145 133 198 106
6 200
192 116 185 143 150 111
6 200
145 111 159 109 182 176
6 200
135 119 108 140 172 143
6 200
173 175 145 170 127 117
6 200
165 114 171 100 129 ...

output:

6645.998796268323531
6969.807543074629393
5496.671919216209062
8830.656827212798817
6563.900207765197592
5810.787032536986771
5623.283738172919584
6138.686830259383896
7096.842057387215391
5474.109373907321242
6870.058474096126702
9145.795396656323646
6860.796304912426422
7405.514431827136832
11535....

result:

ok 500 numbers

Test #6:

score: 0
Accepted
time: 202ms
memory: 3684kb

input:

50
100 2000
1677 1203 1583 1791 1148 1678 1432 1149 1879 1528 1093 1165 1050 1499 1572 1580 1795 1300 1513 1355 1426 1670 1820 1706 1758 1739 1672 1654 1561 1730 1644 1393 1102 1285 1007 1454 1298 1295 1011 1870 1170 1489 1200 1555 1663 1518 1812 1529 1874 1891 1107 1906 1328 1478 1952 1809 1829 103...

output:

209032.262945669470355
226587.601197500422131
209805.529240770963952
129975.370559916074853
132857.585522995272186
140184.690676264639478
145289.581692692270735
225363.295088591345120
77517.701146254330524
151749.567630973819178
220880.897174104902660
157302.894099846424069
137852.775405276130186
20...

result:

ok 50 numbers

Test #7:

score: 0
Accepted
time: 204ms
memory: 3856kb

input:

25
100 4000
3241 3656 1196 3385 1954 2733 2284 2502 1607 2447 2321 2868 3633 2093 1484 1069 3062 2314 2552 3949 2971 2921 2569 3766 2698 1805 1251 1674 1901 2642 3001 3637 2633 3585 1074 2536 1440 3350 3293 2259 1684 1997 2450 1881 1940 2663 2489 3361 3760 2876 3550 1702 3864 2160 3427 2185 2935 232...

output:

39148.764168712914397
40343.603129089744471
33737.405819616600638
35980.497178158890165
50337.099672483120230
34066.526473027741304
34517.410638509660203
40955.975634667767736
44911.628521325073962
35397.786794339277549
38620.367993294676126
44234.251572593610035
37309.660135647172865
43090.98794629...

result:

ok 25 numbers

Test #8:

score: 0
Accepted
time: 179ms
memory: 3676kb

input:

10
1000 10000
3747 2825 6947 9593 4913 4789 6876 8658 5587 3815 9608 5398 4603 4228 1308 2340 6149 7926 5053 7058 5076 6884 7177 7285 1511 8570 8463 4515 8533 5915 3139 8267 1292 4938 4449 8903 1791 3967 5632 5144 6954 2931 1643 2328 4310 7968 3616 8010 7464 1254 1542 2334 4730 9394 8169 8563 2413 5...

output:

32556.212774023639213
32793.363252912931785
34264.447028771675832
32124.210253911300242
32747.001327411642706
32411.876518299584859
32838.391376367690100
32769.933032240085595
32843.263878419573302
31911.106388489573874

result:

ok 10 numbers

Test #9:

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

input:

5
10000 20000
816 7176 11720 19404 2630 12346 12080 6785 12785 7300 585 5996 13354 17594 8322 11897 3679 11553 15700 1103 1789 13177 8348 15058 11351 17220 1793 1319 17367 234 17048 18863 3653 4907 18745 10842 7472 13921 5298 17055 9488 16642 18727 8648 17062 17935 12936 9216 9879 3109 16775 5258 12...

output:

9.921567416492215
17.605041891458253
9.797958971132712
8.785641695402790
11.659223816361019

result:

ok 5 numbers

Test #10:

score: 0
Accepted
time: 165ms
memory: 3788kb

input:

1
50000 100000
26139 26949 70486 12878 81550 21532 41164 20710 97617 91566 95003 39317 87645 61540 56856 77954 77545 78487 93963 60808 9315 31470 54923 71978 37885 47745 34827 73655 51098 44759 19084 15968 12119 71563 45113 27653 82972 24006 33790 36400 29897 38405 71973 61376 16378 58377 10483 4353...

output:

5.332682251925386

result:

ok found '5.332682252', expected '5.332682252', error '0.000000000'

Test #11:

score: 0
Accepted
time: 194ms
memory: 3680kb

input:

1
50000 100000
74907 51418 92110 51191 97802 60679 86079 65117 77937 58169 57954 59000 81034 68864 63761 67056 67354 75390 69109 71430 96093 94749 77968 78911 96369 88694 88042 61376 62416 74366 53329 64597 73647 76952 83758 63370 58462 98302 80642 63048 92322 99304 84461 55499 89704 87614 83090 632...

output:

11180367.837754709646106

result:

ok found '11180367.837754710', expected '11180367.837754710', error '0.000000000'

Test #12:

score: 0
Accepted
time: 166ms
memory: 3720kb

input:

1
50000 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...

output:

2.904737509655563

result:

ok found '2.904737510', expected '2.904737510', error '0.000000000'

Test #13:

score: 0
Accepted
time: 189ms
memory: 3684kb

input:

1
50000 97665
68238 50149 54693 60263 68119 79725 88195 63519 97195 54258 61336 77325 47093 83823 54909 68491 85719 59985 73852 82715 95974 62976 67613 66068 81133 79959 85952 69086 94402 75126 97328 50712 77405 52389 78158 66248 61022 55786 76404 95569 86089 85874 80369 96182 91718 91804 67082 4816...

output:

10104302.693295981734991

result:

ok found '10104302.693295982', expected '10104302.693295982', error '0.000000000'

Test #14:

score: 0
Accepted
time: 194ms
memory: 3684kb

input:

1
50000 100000
62745 71214 86675 86719 67793 58256 58526 74975 82274 80210 61085 96669 66852 78851 60763 61308 72967 56956 72103 78280 59928 57789 69154 85687 97136 66287 99452 93187 87237 64331 72866 51329 77604 85329 85061 51255 58171 84029 93713 90769 89332 81738 60831 67615 60449 64863 71131 732...

output:

11180367.837754709646106

result:

ok found '11180367.837754710', expected '11180367.837754710', error '0.000000000'

Test #15:

score: 0
Accepted
time: 194ms
memory: 3728kb

input:

1
50000 100000
87968 86001 87541 76178 89307 79707 70946 91198 72588 83875 84838 81929 83569 68882 55794 97716 93054 91359 92686 79725 78983 57846 75052 51408 97397 72424 79645 54498 62914 56777 50986 85891 86011 70748 81612 91562 71827 80017 67919 92722 59162 70904 85425 84618 90730 58292 61784 650...

output:

11180367.837754709646106

result:

ok found '11180367.837754710', expected '11180367.837754710', error '0.000000000'

Test #16:

score: 0
Accepted
time: 186ms
memory: 3776kb

input:

1
24993 100000
49999 49998 49997 49996 49995 49994 49993 49992 49991 49990 49989 49988 49987 49986 49985 49984 49983 49982 49981 49980 49979 49978 49977 49976 49975 49974 49973 49972 49971 49970 49969 49968 49967 49966 49965 49964 49963 49962 49961 49960 49959 49958 49957 49956 49955 49954 49953 499...

output:

11180367.837754709646106

result:

ok found '11180367.837754710', expected '11180367.837754710', error '0.000000000'

Test #17:

score: 0
Accepted
time: 180ms
memory: 3712kb

input:

1
49993 100000
33332 33331 33330 33329 33328 33327 33326 33325 33324 33323 33322 33321 33320 33319 33318 33317 33316 33315 33314 33313 33312 33311 33310 33309 33308 33307 33306 33305 33304 33303 33302 33301 33300 33299 33298 33297 33296 33295 33294 33293 33292 33291 33290 33289 33288 33287 33286 332...

output:

6085737.728568816557527

result:

ok found '6085737.728568817', expected '6085737.728568817', error '0.000000000'

Test #18:

score: 0
Accepted
time: 195ms
memory: 3736kb

input:

1
3001 100000
90000 90010 90020 90030 90040 90050 90060 90070 90080 90090 90100 90110 90120 90130 90140 90150 90160 90170 90180 90190 90200 90210 90220 90230 90240 90250 90260 90270 90280 90290 90300 90310 90320 90330 90340 90350 90360 90370 90380 90390 90400 90410 90420 90430 90440 90450 90460 9047...

output:

9624909.165092153474689

result:

ok found '9624909.165092153', expected '9624909.165092153', error '0.000000000'

Test #19:

score: 0
Accepted
time: 194ms
memory: 3820kb

input:

1
6001 100000
90000 90005 90010 90015 90020 90025 90030 90035 90040 90045 90050 90055 90060 90065 90070 90075 90080 90085 90090 90095 90100 90105 90110 90115 90120 90125 90130 90135 90140 90145 90150 90155 90160 90165 90170 90175 90180 90185 90190 90195 90200 90205 90210 90215 90220 90225 90230 9023...

output:

9624477.520494615659118

result:

ok found '9624477.520494616', expected '9624477.520494616', error '0.000000000'

Test #20:

score: 0
Accepted
time: 192ms
memory: 3760kb

input:

1
9001 100000
85000 85005 85010 85015 85020 85025 85030 85035 85040 85045 85050 85055 85060 85065 85070 85075 85080 85085 85090 85095 85100 85105 85110 85115 85120 85125 85130 85135 85140 85145 85150 85155 85160 85165 85170 85175 85180 85185 85190 85195 85200 85205 85210 85215 85220 85225 85230 8523...

output:

9647833.164822876453400

result:

ok found '9647833.164822876', expected '9647833.164822876', error '0.000000000'

Test #21:

score: 0
Accepted
time: 192ms
memory: 3868kb

input:

1
2251 100000
85000 85020 85040 85060 85080 85100 85120 85140 85160 85180 85200 85220 85240 85260 85280 85300 85320 85340 85360 85380 85400 85420 85440 85460 85480 85500 85520 85540 85560 85580 85600 85620 85640 85660 85680 85700 85720 85740 85760 85780 85800 85820 85840 85860 85880 85900 85920 8594...

output:

9094171.644422868266702

result:

ok found '9094171.644422868', expected '9094171.644422868', error '0.000000000'