結果

問題 No.5020 Averaging
ユーザー ldsyb
提出日時 2024-02-25 15:47:00
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,011 bytes
コンパイル時間 5,932 ms
コンパイル使用メモリ 337,228 KB
実行使用メモリ 726,352 KB
スコア 0
最終ジャッジ日時 2024-02-25 15:48:10
合計ジャッジ時間 64,859 ms
ジャッジサーバーID
(参考情報)
judge15 / judge10
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other TLE * 49 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
int main() {
const auto start = steady_clock::now();
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
int64_t n;
cin >> n;
vector<int64_t> as(n), bs(n);
for (int64_t i = 0; i < n; i++) {
cin >> as[i] >> bs[i];
}
random_device rnd;
mt19937 engine(rnd());
uniform_int_distribution<> randn(0, n - 1);
int64_t c = 500000000000000000LL;
auto calc_score = [&] {
return int64_t(2000000 -
100000 * log10(max(abs(as[0] - c), abs(bs[0] - c)) + 1));
};
auto f = [&](int64_t a, int64_t b) { return max(abs(a - c), abs(b - c)); };
pair<int64_t, int64_t> p = {2 * c - as[0], 2 * c - bs[0]};
auto g = [&](int64_t a, int64_t b) {
return 2 * logl(abs(a - p.first) + abs(b - p.second)) /
(logl(2 * abs(a - p.first)) + logl(abs(b - p.second)));
};
using T = pair<pair<long double, vector<int64_t>>,
pair<vector<int64_t>, vector<int64_t>>>;
vector<priority_queue<T, vector<T>, greater<>>> pqs(50);
for (int64_t i = 1; i < n; i++) {
vector<int64_t> v;
v.push_back(i);
pqs[0].push({{g(as[i], bs[i]), v}, {as, bs}});
}
long double s = (1LL << 60);
vector<int64_t> xs;
while (duration_cast<milliseconds>(steady_clock::now() - start).count() <
800) {
for (int64_t i = 0; i < 50; i++) {
if (pqs[i].empty()) {
continue;
}
auto [pp, qq] = pqs[i].top();
pqs[i].pop();
auto [d, v] = pp;
auto [cs, ds] = qq;
if (d < s) {
s = d;
xs = v;
}
if (i + 1 < 50) {
for (int64_t k = 1; k < n; k++) {
if (v.back() == k) {
continue;
}
int64_t j = v.back();
v.push_back(k);
int64_t w = cs[j], x = ds[j];
int64_t y = cs[k], z = ds[k];
cs[j] = cs[k] = (w + x) / 2;
ds[j] = ds[k] = (y + z) / 2;
pqs[i + 1].push({{g(cs[k], ds[k]), v}, {cs, ds}});
cs[j] = w;
ds[j] = x;
cs[k] = y;
ds[k] = z;
v.pop_back();
}
}
}
}
vector<int64_t> us, vs;
for (int64_t i = 1; i < xs.size(); i++) {
us.push_back(xs[i - 1] + 1);
vs.push_back(xs[i] + 1);
}
us.push_back(1);
vs.push_back([&] {
int64_t ret = 1;
for (int64_t i = 2; i < n; i++) {
int64_t x = (as[0] + as[i]) / 2;
int64_t y = (bs[0] + bs[i]) / 2;
int64_t a = (as[0] + as[ret]) / 2;
int64_t b = (bs[0] + bs[ret]) / 2;
if (f(x, y) < f(a, b)) {
ret = i;
}
}
ret++;
return ret;
}());
cout << us.size() << '\n';
for (int64_t i = 0; i < us.size(); i++) {
cout << us[i] << ' ' << vs[i] << '\n';
}
// cerr << calc_score() << endl;
// for (int64_t i = 0; i < n; i++) {
// cerr << as[i] << ' ' << bs[i] << endl;
// }
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0