QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#736722 | #5136. Lowest Latency | nicksms# | WA | 683ms | 6248kb | C++17 | 1.3kb | 2024-11-12 12:50:23 | 2024-11-12 12:50:24 |
Judging History
answer
/**
* Author: Nicholas Winschel
* Created: 11.11.2024 23:38:24
**/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())
#define each(a,b) for (auto &a : b)
ll bes = 8e18;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int MAXN = 1e5+5;
ll x[MAXN], y[MAXN], z[MAXN];
void tr(int i, int j) {
bes = min(bes, (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]));
}
int main() {
cin.tie(0)->sync_with_stdio(0); // initialize fast I/O
int n; cin >> n;
for (int i = 0; i < n; i++)
cin >> x[i] >> y[i] >> z[i];
vi inds(n);
iota(inds.begin(), inds.end(), 0);
uniform_int_distribution<ll> rnd(-1e9, 1e9);
for (int _ = 0; _ < 50; _++) {
ll mx = rnd(rng), my = rnd(rng), mz = rnd(rng);
sort(inds.begin(), inds.end(), [&](int i, int j) {
return mx*x[i] + my*y[i] + mz*z[i] < mx*x[j] + my*y[j] + mz*z[j];
});
for (int i = 0; i+1 < n; i++)
tr(inds[i], inds[i+1]);
}
cout << fixed << setprecision(15) << sqrtl(bes);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 682ms
memory: 6236kb
input:
100000 332143901 284102352 570195534 434050088 127258259 405899431 771419785 591983836 993571739 840022894 817836335 522977053 838660826 594804134 22555488 479844553 644693351 113265148 856575556 931653385 248482595 167010514 77957036 379182090 563518287 572234979 55605040 653604447 286132667 814469...
output:
315317.985436923657886
result:
ok found '315317.9854369', expected '315317.9854369', error '0.0000000'
Test #2:
score: 0
Accepted
time: 683ms
memory: 6248kb
input:
100000 294674684 621978223 936886711 729706184 257011600 509475108 255284311 928497631 943121348 999571509 649085458 190336855 724896004 566691798 900489171 787916786 938048446 716801523 919466219 922219328 171033785 821424684 730740051 584718063 703013850 378192728 999449221 803098909 930625401 764...
output:
460312.368161013027532
result:
ok found '460312.3681610', expected '460312.3681610', error '0.0000000'
Test #3:
score: 0
Accepted
time: 681ms
memory: 6112kb
input:
100000 68066504 607422014 604154531 298243249 809117974 378127039 902111766 904477266 88612244 112870244 573634331 476586362 121457650 137970427 888937448 814503981 599217627 41586661 657725475 792552763 286458036 128591734 317780776 735217933 426434903 267716721 797445083 356941701 640898753 989717...
output:
227505.369690475657578
result:
ok found '227505.3696905', expected '227505.3696905', error '0.0000000'
Test #4:
score: -100
Wrong Answer
time: 683ms
memory: 6240kb
input:
100000 783814852 607989927 238270593 479634451 745483211 114966027 325082774 824243998 684370276 913116840 873616206 663947124 935685800 849048463 561116787 225523433 151485268 624035618 888263624 217496177 147206736 540507934 416222602 836535347 127914716 340560041 316609317 321225449 482238200 500...
output:
252454.549958997570059
result:
wrong answer 1st numbers differ - expected: '146350.7936364', found: '252454.5499590', error = '0.7249961'