QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#870251 | #8614. 3D | ucup-team987# | WA | 2800ms | 4224kb | C++20 | 7.1kb | 2025-01-25 15:33:02 | 2025-01-25 15:33:06 |
Judging History
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