QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#870251#8614. 3Ducup-team987#WA 2800ms4224kbC++207.1kb2025-01-25 15:33:022025-01-25 15:33:06

Judging History

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

  • [2025-01-25 15:33:06]
  • 评测
  • 测评结果:WA
  • 用时:2800ms
  • 内存:4224kb
  • [2025-01-25 15:33:02]
  • 提交

answer

#if __INCLUDE_LEVEL__ == 0

#include __BASE_FILE__

Xorshift rnd;

void Solve() {
  int n;
  IN(n);
  vector d(n, vector<double>(n));
  IN(d);

  vector<array<double, 3>> p(n);
  for (int i : Rep(0, n)) {
    ranges::generate(p[i], LIFT(rnd.Uniform));
  }

  auto Eval = [&](double) -> double {
    double mx = 0;
    double sum = 0;
    for (int i : Rep(0, n)) {
      for (int j : Rep(i + 1, n)) {
        double db = hypot(p[j][0] - p[i][0],
                          p[j][1] - p[i][1],
                          p[j][2] - p[i][2]);
        // SetMax(mx, abs(db - d[i][j]));
        sum += (db - d[i][j]) * (db - d[i][j]);
      }
    }
    // return sqrt(sum) * (1 - t) + mx;
    return sum;
  };

  PARAM(double, TL, 2.8);
  PARAM(double, T0, 1.0);
  PARAM(double, T1, 1e-5);

  double cur = Eval(0.0);

  double best = cur;
  auto best_p = p;

  for (const auto& sa : SimulatedAnnealing<256>(rnd, TL, T0, T1)) {
    int i = rnd.Int(0, n - 1);
    int axis = rnd.Int(0, 2);
    double L = pow(0.01, 1.0 - sa.cur_time) * pow(0.001, sa.cur_time);
    double delta = rnd.Uniform(-L, L);
    // double nxt = Eval(sa.cur_time);
    double nxt = cur;
    for (int j : Rep(0, n) | FILTER(j, j != i)) {
      double db = hypot(p[j][0] - p[i][0],
                        p[j][1] - p[i][1],
                        p[j][2] - p[i][2]);
      nxt -= (db - d[i][j]) * (db - d[i][j]);
    }
    p[i][axis] += delta;
    for (int j : Rep(0, n) | FILTER(j, j != i)) {
      double db = hypot(p[j][0] - p[i][0],
                        p[j][1] - p[i][1],
                        p[j][2] - p[i][2]);
      nxt += (db - d[i][j]) * (db - d[i][j]);
    }

    if (nxt > cur + sa.tol) {
      p[i][axis] -= delta;
    } else {
      cur = nxt;
    }

    if (SetMin(best, cur)) {
      best_p = p;
      if ([&] {
            double mx = 0;
            for (int i : Rep(0, n)) {
              for (int j : Rep(i + 1, n)) {
                double db = hypot(p[j][0] - p[i][0],
                                  p[j][1] - p[i][1],
                                  p[j][2] - p[i][2]);
                if (abs(db - d[i][j]) > 0.0999999) {
                  return false;
                }
              }
            }
            return true;
          }()) {
        break;
      }
      cur = Eval(0.0);
    }
  }

  OUT(best_p);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  Solve();
}

#elif __INCLUDE_LEVEL__ == 1

#include <bits/stdc++.h>

__attribute__((constructor)) inline double ElapsedTime() {
  using namespace std::chrono;
  static const auto T0 = steady_clock::now();
  return duration<double>(steady_clock::now() - T0).count();
}

class Xorshift {
 public:
  using result_type = uint64_t;
  static constexpr result_type min() { return 0; }
  static constexpr result_type max() { return UINT64_MAX; }
  result_type operator()() { return Next(); }

  Xorshift() : Xorshift(std::chrono::steady_clock::now().time_since_epoch().count()) {}

  explicit Xorshift(uint64_t seed) {
    std::ranges::generate(x_, std::mt19937_64(seed));
  }

  uint64_t Next() {
    if (++p_ == N) {
      p_ = 0;
      for (int i = 0; i < N; ++i) {
        x_[i] ^= x_[i] << 7;
        x_[i] ^= x_[i] >> 9;
      }
    }
    return x_[p_];
  }

  int Int(int a, int b) {
    uint64_t r = Next() >> 32;
    return a + int(r * (b - a + 1) >> 32);
  }

  int64_t Int(int64_t a, int64_t b) {
    __uint128_t r = Next();
    return a + int64_t(r * (b - a + 1) >> 64);
  }

  std::pair<int, int> Int2(int a, int b) {
    auto r = std::bit_cast<std::array<uint32_t, 2>>(Next());
    int x = a + int(r[0] * uint64_t(b - a) >> 32);
    int y = a + int(r[1] * uint64_t(b - a + 1) >> 32);
    if (y == x) {
      y = b;
    } else if (y < x) {
      std::swap(x, y);
    }
    return {x, y};
  }

  double Uniform() {
    return double(Next()) / double(UINT64_MAX);
  }

  double Uniform(double a, double b) {
    return a + Uniform() * (b - a);
  }

 private:
  static constexpr int N = 8;

  std::array<uint64_t, N> x_;
  int p_ = -1;
};

template <class D>
class RangeBase {
  struct I {
    D* self;
    bool operator!=(int) const { return self->IsValid(); }
    void operator++() { self->Advance(); }
    auto operator*() const { return self->Get(); }
  };

 public:
  I begin() { return {static_cast<D*>(this)}; }
  int end() const { return 0; }
};

template <int UpdateInterval = 1>
class SimulatedAnnealing : public RangeBase<SimulatedAnnealing<UpdateInterval>> {
 public:
  SimulatedAnnealing(Xorshift& rnd, double time_limit, double start_temp, double end_temp)
      : rnd_(&rnd),
        start_time_(ElapsedTime()),
        time_limit_(time_limit),
        start_temp_(start_temp),
        cooling_rate_(start_temp > 0.0 ? end_temp / start_temp : 1.0),
        iter_(0),
        cur_time_(0.0),
        temp_(start_temp) {
    assert(0.0 <= end_temp && end_temp <= start_temp);
  }

 private:
  friend RangeBase<SimulatedAnnealing>;

  bool IsValid() const {
    return cur_time_ < 1.0;
  }

  void Advance() {
    if (++iter_ % UpdateInterval == 0) {
      cur_time_ = (ElapsedTime() - start_time_) / time_limit_;
      temp_ = start_temp_ * std::pow(cooling_rate_, cur_time_);
    }
  }

  auto Get() const {
    struct {
      int64_t iter;
      double cur_time;
      double temp;
      double tol;
    } ret{iter_, cur_time_, temp_, temp_ * -std::log(rnd_->Uniform())};
    return ret;
  }

  Xorshift* rnd_;
  double start_time_;
  double time_limit_;
  double start_temp_;
  double cooling_rate_;
  int64_t iter_;
  double cur_time_;
  double temp_;
};

template <class T> concept Range = std::ranges::range<T> && !std::convertible_to<T, std::string_view>;
template <class T> concept Tuple = std::__is_tuple_like<T>::value && !Range<T>;

namespace std {

istream& operator>>(istream& is, Range auto&& r) {
  for (auto&& e : r) is >> e;
  return is;
}
istream& operator>>(istream& is, Tuple auto&& t) {
  apply([&](auto&... xs) { (is >> ... >> xs); }, t);
  return is;
}

ostream& operator<<(ostream& os, Range auto&& r) {
  auto sep = "";
  for (auto&& e : r) os << exchange(sep, " ") << e;
  return os;
}
ostream& operator<<(ostream& os, Tuple auto&& t) {
  auto sep = "";
  apply([&](auto&... xs) { ((os << exchange(sep, " ") << xs), ...); }, t);
  return os;
}

}  // namespace std

using namespace std;

#define LAMBDA(x, ...) ([&](auto&& x) -> decltype(auto) { return __VA_ARGS__; })
#define LAMBDA2(x, y, ...) ([&](auto&& x, auto&& y) -> decltype(auto) { return __VA_ARGS__; })
#define LIFT(f) ([&](auto&&... xs) -> decltype(auto) { return f(forward<decltype(xs)>(xs)...); })
#define FILTER(...) views::filter(LAMBDA(__VA_ARGS__))
#define Rep(...) [](int l, int r) { return views::iota(min(l, r), r); }(__VA_ARGS__)
#define SetMin(...) LAMBDA2(x, y, y < x && (x = y, 1))(__VA_ARGS__)
#define PARAM(T, NAME, val) constexpr T NAME = val
#define IN(...) (cin >> forward_as_tuple(__VA_ARGS__))
#define OUT(...) (cout << forward_as_tuple(__VA_ARGS__) << '\n')

#endif  // __INCLUDE_LEVEL__ == 1

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 48ms
memory: 4224kb

input:

4
0.000000 0.758400 0.557479 0.379026
0.758400 0.000000 0.516608 0.446312
0.557479 0.516608 0.000000 0.554364
0.379026 0.446312 0.554364 0.000000

output:

-0.226554 1.88449 1.29068 0.197853 2.58147 1.50504 -0.20709 2.39748 1.07932 0.0775391 2.05903 1.53833

result:

ok OK. Max delta: 0.099078

Test #2:

score: 0
Accepted
time: 2800ms
memory: 4224kb

input:

1
0.000000

output:

0.893779 0.161884 0.0624319

result:

ok OK. Max delta: 0.000000

Test #3:

score: 0
Accepted
time: 0ms
memory: 4096kb

input:

2
0.000000 0.938096
0.938096 0.000000

output:

0.900851 0.583856 0.794665 0.697793 -0.125833 0.396867

result:

ok OK. Max delta: 0.099565

Test #4:

score: 0
Accepted
time: 7ms
memory: 4224kb

input:

3
0.000000 0.769195 0.308169
0.769195 0.000000 0.686850
0.308169 0.686850 0.000000

output:

0.271926 0.507446 0.183188 0.232111 0.63552 0.943622 0.447577 0.320028 0.496403

result:

ok OK. Max delta: 0.098662

Test #5:

score: 0
Accepted
time: 798ms
memory: 4224kb

input:

5
0.000000 0.444506 0.292333 0.209539 1.195824
0.444506 0.000000 0.220873 0.748833 0.757486
0.292333 0.220873 0.000000 0.533499 0.797167
0.209539 0.748833 0.533499 0.000000 1.141148
1.195824 0.757486 0.797167 1.141148 0.000000

output:

1.29004 0.725638 0.989632 1.09406 0.462623 1.42241 1.05265 0.662378 1.24922 1.21938 0.98175 0.941218 0.264658 0.484056 1.53817

result:

ok OK. Max delta: 0.098524

Test #6:

score: 0
Accepted
time: 1023ms
memory: 4224kb

input:

6
0.000000 0.932377 0.787009 0.996894 0.763544 0.651377
0.932377 0.000000 0.421278 1.155673 1.149686 0.508563
0.787009 0.421278 0.000000 0.709021 0.793974 0.224884
0.996894 1.155673 0.709021 0.000000 0.392548 0.957498
0.763544 1.149686 0.793974 0.392548 0.000000 0.714079
0.651377 0.508563 0.224884 0...

output:

1.57339 1.72948 -1.49305 1.76419 2.62416 -1.25812 1.49477 2.38553 -1.03827 1.4914 1.86921 -0.438966 1.5045 1.61865 -0.772416 1.40575 2.23251 -1.25648

result:

ok OK. Max delta: 0.082031

Test #7:

score: 0
Accepted
time: 970ms
memory: 4224kb

input:

7
0.000000 0.688481 0.455407 0.777049 0.963980 0.255052 0.554599
0.688481 0.000000 0.596921 0.827787 1.260207 0.340235 0.493011
0.455407 0.596921 0.000000 0.609173 0.640567 0.352193 0.243913
0.777049 0.827787 0.609173 0.000000 0.858134 0.701131 0.393303
0.963980 1.260207 0.640567 0.858134 0.000000 0...

output:

-0.252946 -0.0119324 -1.30914 0.466368 -0.163915 -1.33933 -0.108447 -0.387865 -1.30385 -0.0699854 -0.527768 -0.803368 -0.399116 -0.941889 -1.47534 0.0825743 -0.11266 -1.30202 0.132281 -0.45921 -1.16797

result:

ok OK. Max delta: 0.095334

Test #8:

score: 0
Accepted
time: 963ms
memory: 4224kb

input:

8
0.000000 0.437494 0.934265 0.074097 0.673669 0.425700 0.479212 0.679270
0.437494 0.000000 0.331045 0.393801 0.527073 0.402792 0.375134 0.461133
0.934265 0.331045 0.000000 0.792317 0.605663 0.880433 0.786178 0.455534
0.074097 0.393801 0.792317 0.000000 0.681633 0.278020 0.327267 0.550058
0.673669 0...

output:

0.827238 0.887856 -1.54579 1.09537 0.54129 -1.24401 1.2686 0.570793 -0.873051 0.847584 0.755715 -1.57741 1.28446 1.0378 -1.20016 1.02984 0.62075 -1.65506 0.851741 0.503642 -1.49487 0.796668 0.482015 -1.01564

result:

ok OK. Max delta: 0.094553

Test #9:

score: 0
Accepted
time: 1093ms
memory: 4096kb

input:

9
0.000000 0.883128 0.449200 0.525234 0.745161 0.323207 0.430759 1.247103 0.564870
0.883128 0.000000 0.664206 0.590150 0.433578 0.890708 0.741718 0.798316 1.033522
0.449200 0.664206 0.000000 0.326949 0.636800 0.523900 0.642051 0.680925 0.349474
0.525234 0.590150 0.326949 0.000000 0.523965 0.344241 0...

output:

-0.0652719 0.117359 0.391031 -0.0876104 0.80342 -0.08255 0.341241 0.371681 0.262422 0.101217 0.510133 0.348275 0.0766285 0.437918 -0.247289 -0.00177221 0.406227 0.629935 -0.0341907 0.0284901 -0.0887876 0.682153 0.952439 -0.0851091 0.481255 0.0461004 0.152784

result:

ok OK. Max delta: 0.096494

Test #10:

score: 0
Accepted
time: 1250ms
memory: 4224kb

input:

10
0.000000 1.141963 0.357381 0.960442 0.887799 0.393165 1.000015 0.883861 1.059968 0.666258
1.141963 0.000000 0.730979 0.430440 0.528721 0.822481 0.567380 0.334929 0.552413 0.840500
0.357381 0.730979 0.000000 0.861027 0.623726 0.216981 0.719423 0.558824 0.726378 0.310217
0.960442 0.430440 0.861027 ...

output:

0.703481 0.0470734 -0.0257289 0.710479 -1.01762 0.217022 0.78239 -0.283436 -0.0548957 0.654553 -0.742326 0.598399 0.362074 -0.719542 -0.0436811 0.907228 -0.203424 0.133736 0.563096 -0.681272 0.538465 0.49679 -0.769008 0.124458 0.888096 -0.926524 -0.322017 0.959467 -0.522541 -0.333016

result:

ok OK. Max delta: 0.097065

Test #11:

score: 0
Accepted
time: 1161ms
memory: 4224kb

input:

10
0.000000 0.508467 0.359704 0.705660 0.752608 0.632298 0.433047 0.541855 0.108842 0.652503
0.508467 0.000000 0.849608 0.542157 0.614068 0.673963 0.552462 0.470005 0.697815 0.822930
0.359704 0.849608 0.000000 0.832286 0.790254 0.844729 0.428335 0.707356 0.221649 0.447522
0.705660 0.542157 0.832286 ...

output:

0.660865 0.0936509 1.60193 0.940916 -0.165885 1.24655 0.437683 0.443954 1.6036 0.593574 0.0479482 0.920818 0.935191 0.401818 0.937807 0.715933 -0.417584 1.76979 0.773071 0.441072 1.29521 0.964347 0.244008 1.25667 0.597965 0.239849 1.54589 0.30945 0.326363 1.19056

result:

ok OK. Max delta: 0.099392

Test #12:

score: 0
Accepted
time: 1416ms
memory: 4224kb

input:

10
0.000000 0.532841 1.081715 0.791902 0.304710 0.943952 0.318604 0.512618 0.263399 0.317304
0.532841 0.000000 0.617254 0.571776 0.863445 0.644868 0.534570 0.898453 0.767957 0.380512
1.081715 0.617254 0.000000 0.498716 1.118400 0.375946 0.739541 1.081104 0.985516 0.778030
0.791902 0.571776 0.498716 ...

output:

2.22408 1.07196 0.500082 1.96354 1.58029 0.643935 1.73944 1.94427 0.166914 1.57592 1.39837 0.269198 2.39469 1.02457 0.216439 1.60696 1.62203 0.105053 1.92712 1.21443 0.291018 2.38651 1.0248 0.0687583 2.32559 1.11748 0.224175 2.27621 1.39638 0.398292

result:

ok OK. Max delta: 0.099968

Test #13:

score: 0
Accepted
time: 1172ms
memory: 4224kb

input:

10
0.000000 0.337812 0.820740 0.714576 0.958294 1.114603 1.052855 0.816204 0.921684 0.581533
0.337812 0.000000 0.588126 0.550959 0.851936 1.076003 0.824637 0.634512 0.630209 0.781504
0.820740 0.588126 0.000000 0.754545 0.853344 0.651402 0.625435 0.521290 0.463145 0.927492
0.714576 0.550959 0.754545 ...

output:

1.59896 0.0315819 0.426789 1.46306 0.0278678 0.756943 1.43981 -0.360491 1.23234 1.45967 -0.5857 0.609352 2.24507 -0.117895 1.07099 2.00618 -0.724693 1.1743 2.09861 -0.456022 1.19194 1.91291 -0.286438 1.10088 1.78975 -0.0953039 1.37839 1.51861 -0.594892 0.337675

result:

ok OK. Max delta: 0.093343

Test #14:

score: 0
Accepted
time: 1272ms
memory: 4224kb

input:

10
0.000000 0.157221 0.630350 0.940948 0.790907 0.666502 0.536584 0.506196 0.353744 0.642539
0.157221 0.000000 0.582092 1.279081 0.812532 0.810677 0.850103 0.865478 0.320962 0.694578
0.630350 0.582092 0.000000 1.171965 1.045437 1.168568 0.582206 0.854963 0.513105 1.137099
0.940948 1.279081 1.171965 ...

output:

0.387989 0.760037 0.125153 0.328488 0.541404 0.190359 0.592814 0.813007 0.67037 0.462878 1.74803 0.0501258 -0.258533 1.20078 0.167873 -0.10678 1.03545 -0.239421 0.416186 1.31277 0.351542 0.334382 1.36035 0.123296 0.172587 0.744055 0.324534 0.0476081 0.884152 -0.332687

result:

ok OK. Max delta: 0.098198

Test #15:

score: 0
Accepted
time: 1649ms
memory: 4096kb

input:

10
0.000000 0.655953 0.416075 0.956128 0.351321 0.411663 0.904277 0.786858 0.961004 1.159073
0.655953 0.000000 0.398507 0.430374 0.378366 0.531641 0.789955 0.396050 0.368849 1.088933
0.416075 0.398507 0.000000 0.976294 0.461240 0.328488 0.979923 0.705916 0.884932 1.254989
0.956128 0.430374 0.976294 ...

output:

0.550873 -0.790557 0.779333 0.898053 -0.394167 1.01279 0.898697 -0.746005 0.671477 0.994501 0.0243248 1.09157 0.630172 -0.452754 0.80235 0.688307 -0.51577 0.522133 0.486679 0.142701 0.689446 1.13819 -0.216808 1.09552 0.726372 -0.0459094 1.23241 0.146282 0.267558 0.646113

result:

ok OK. Max delta: 0.093648

Test #16:

score: 0
Accepted
time: 1225ms
memory: 4224kb

input:

10
0.000000 0.672245 0.576475 0.810904 0.599396 0.493165 0.431514 0.511677 0.859634 0.881368
0.672245 0.000000 1.249406 1.027657 0.113558 0.392208 0.862698 0.329856 1.012059 1.039747
0.576475 1.249406 0.000000 0.869439 1.254676 1.087547 0.535956 1.182094 0.744887 0.645939
0.810904 1.027657 0.869439 ...

output:

1.60308 0.763708 0.384895 1.4585 1.36995 0.237602 1.24753 0.228606 0.518433 0.953116 0.659979 -0.110727 1.453 1.36732 0.114438 1.59198 1.18786 0.591255 1.2052 0.654369 0.364848 1.78438 1.26075 0.384049 0.91273 0.602911 -0.0869004 0.746378 0.663186 0.222419

result:

ok OK. Max delta: 0.093017

Test #17:

score: 0
Accepted
time: 1285ms
memory: 4224kb

input:

10
0.000000 0.609276 0.612588 0.898616 0.668529 0.802163 0.126104 0.681054 0.761434 0.310892
0.609276 0.000000 0.922363 0.423227 0.591390 0.662160 0.751720 0.241917 0.563127 0.693959
0.612588 0.922363 0.000000 0.873479 0.681583 0.707351 0.595097 0.923846 0.768951 0.393683
0.898616 0.423227 0.873479 ...

output:

0.180538 0.525779 -0.262805 -0.39411 0.342968 -0.473205 0.0851861 0.362093 0.365659 -0.455184 -0.0938898 -0.251965 -0.146271 -0.0529767 -0.118875 -0.317095 -0.127216 -0.0233164 0.221198 0.417241 -0.185911 -0.289582 0.0926447 -0.363973 -0.16968 -0.0719082 -0.192635 0.133367 0.41339 -0.061005

result:

ok OK. Max delta: 0.098605

Test #18:

score: -100
Wrong Answer
time: 2799ms
memory: 4224kb

input:

10
0.000000 0.542508 0.426558 0.741404 0.733105 0.586307 0.271270 0.847645 0.757695 0.830800
0.542508 0.000000 0.497136 1.012191 1.083431 0.944439 0.618287 0.696705 0.472089 0.354373
0.426558 0.497136 0.000000 0.973354 0.928175 0.884683 0.594828 0.699473 0.534409 0.737409
0.741404 1.012191 0.973354 ...

output:

0.62148 0.238717 -0.247567 0.302329 -0.199078 -0.17242 0.137768 0.1622 -0.141708 1.00423 -0.008367 0.390762 0.765509 0.507865 0.429284 0.728755 0.503507 0.289182 0.579815 0.468806 -0.252449 0.452537 -0.0282188 0.510148 0.282167 0.0514056 0.331577 0.436936 -0.537191 -0.169893

result:

wrong answer Expected distance between 1 and 6 is 0.618287, but found 0.727648