QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#736722#5136. Lowest Latencynicksms#WA 683ms6248kbC++171.3kb2024-11-12 12:50:232024-11-12 12:50:24

Judging History

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

  • [2024-11-12 12:50:24]
  • 评测
  • 测评结果:WA
  • 用时:683ms
  • 内存:6248kb
  • [2024-11-12 12:50:23]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'