結果
問題 | No.5020 Averaging |
ユーザー |
![]() |
提出日時 | 2024-02-25 15:35:27 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,999 bytes |
コンパイル時間 | 6,567 ms |
コンパイル使用メモリ | 338,044 KB |
実行使用メモリ | 814,928 KB |
スコア | 0 |
最終ジャッジ日時 | 2024-02-25 15:36:40 |
合計ジャッジ時間 | 13,315 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 48 MLE * 2 |
ソースコード
#include <bits/stdc++.h>using namespace std;using namespace chrono;#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#endifint 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() <900) {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;}