QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#736724 | #5136. Lowest Latency | nicksms# | WA | 676ms | 6184kb | C++17 | 1.3kb | 2024-11-12 12:51:00 | 2024-11-12 12:51:01 |
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: 676ms
memory: 6108kb
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: -100
Wrong Answer
time: 670ms
memory: 6184kb
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:
507472.477243840289049
result:
wrong answer 1st numbers differ - expected: '460312.3681610', found: '507472.4772438', error = '0.1024524'