QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#196433 | #7239. Triangle | jeffqi | AC ✓ | 219ms | 3868kb | C++20 | 2.0kb | 2023-10-01 17:24:03 | 2023-10-01 17:24:04 |
Judging History
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'