QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#736724#5136. Lowest Latencynicksms#WA 676ms6184kbC++171.3kb2024-11-12 12:51:002024-11-12 12:51:01

Judging History

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

  • [2024-11-12 12:51:01]
  • 评测
  • 测评结果:WA
  • 用时:676ms
  • 内存:6184kb
  • [2024-11-12 12:51:00]
  • 提交

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: 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'