結果
問題 | No.5020 Averaging |
ユーザー |
![]() |
提出日時 | 2024-02-25 16:53:32 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,000 bytes |
コンパイル時間 | 5,780 ms |
コンパイル使用メモリ | 316,448 KB |
実行使用メモリ | 6,548 KB |
スコア | 10,011,445 |
最終ジャッジ日時 | 2024-02-25 16:56:12 |
合計ジャッジ時間 | 53,195 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 WA * 22 |
ソースコード
#include <bits/stdc++.h>#include <queue>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);uniform_int_distribution<> rand1n(1, 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]};int64_t s = numeric_limits<int64_t>::max();vector<int64_t> xs;while (duration_cast<milliseconds>(steady_clock::now() - start).count() <900) {int64_t sz = rand1n(engine);vector<int64_t> ys(sz);ys[0] = rand1n(engine);for (int64_t i = 1; i < sz; i++) {ys[i] = rand1n(engine);}vector<int64_t> cs(as), ds(bs);for (int64_t i = 1; i < ys.size(); i++) {int64_t x = (cs[ys[i - 1]] + cs[ys[i]]) / 2;int64_t y = (ds[ys[i - 1]] + ds[ys[i]]) / 2;cs[ys[i - 1]] = cs[ys[i]] = x;ds[ys[i - 1]] = ds[ys[i]] = y;}int64_t i = [&] {int64_t ret = 1;for (int64_t i = 2; i < n; i++) {int64_t x = (cs[0] + cs[i]) / 2;int64_t y = (ds[0] + ds[i]) / 2;int64_t a = (cs[0] + cs[ret]) / 2;int64_t b = (ds[0] + ds[ret]) / 2;if (f(x, y) < f(a, b)) {ret = i;}}return ret;}();cs[0] = (cs[0] + cs[i]) / 2;ds[0] = (ds[0] + ds[i]) / 2;if (f(cs[0], ds[0]) < s) {s = f(cs[0], ds[0]);xs = ys;}}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';}// for (int64_t i = 0; i < us.size(); i++) {// int64_t x = (as[us[i] - 1] + as[vs[i] - 1]) / 2;// int64_t y = (bs[us[i] - 1] + bs[vs[i] - 1]) / 2;// as[us[i] - 1] = as[vs[i] - 1] = x;// bs[us[i] - 1] = bs[vs[i] - 1] = y;// }// cerr << calc_score() << endl;// for (int64_t i = 0; i < n; i++) {// cerr << i << ' ' << as[i] << ' ' << bs[i] << endl;// }return 0;}