結果

問題 No.5020 Averaging
ユーザー ldsybldsyb
提出日時 2024-02-25 16:59:01
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 903 ms / 1,000 ms
コード長 3,105 bytes
コンパイル時間 5,908 ms
コンパイル使用メモリ 316,444 KB
実行使用メモリ 6,676 KB
スコア 16,431,994
最終ジャッジ日時 2024-02-25 17:01:36
合計ジャッジ時間 53,640 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 902 ms
6,676 KB
testcase_01 AC 901 ms
6,676 KB
testcase_02 AC 903 ms
6,676 KB
testcase_03 AC 903 ms
6,676 KB
testcase_04 AC 902 ms
6,676 KB
testcase_05 AC 902 ms
6,676 KB
testcase_06 AC 902 ms
6,676 KB
testcase_07 AC 901 ms
6,676 KB
testcase_08 AC 902 ms
6,676 KB
testcase_09 AC 902 ms
6,676 KB
testcase_10 AC 902 ms
6,676 KB
testcase_11 AC 902 ms
6,676 KB
testcase_12 AC 902 ms
6,676 KB
testcase_13 AC 903 ms
6,676 KB
testcase_14 AC 902 ms
6,676 KB
testcase_15 AC 902 ms
6,676 KB
testcase_16 AC 902 ms
6,676 KB
testcase_17 AC 901 ms
6,676 KB
testcase_18 AC 902 ms
6,676 KB
testcase_19 AC 902 ms
6,676 KB
testcase_20 AC 902 ms
6,676 KB
testcase_21 AC 902 ms
6,676 KB
testcase_22 AC 902 ms
6,676 KB
testcase_23 AC 902 ms
6,676 KB
testcase_24 AC 902 ms
6,676 KB
testcase_25 AC 902 ms
6,676 KB
testcase_26 AC 902 ms
6,676 KB
testcase_27 AC 902 ms
6,676 KB
testcase_28 AC 902 ms
6,676 KB
testcase_29 AC 902 ms
6,676 KB
testcase_30 AC 902 ms
6,676 KB
testcase_31 AC 902 ms
6,676 KB
testcase_32 AC 901 ms
6,676 KB
testcase_33 AC 903 ms
6,676 KB
testcase_34 AC 902 ms
6,676 KB
testcase_35 AC 902 ms
6,676 KB
testcase_36 AC 902 ms
6,676 KB
testcase_37 AC 901 ms
6,676 KB
testcase_38 AC 902 ms
6,676 KB
testcase_39 AC 902 ms
6,676 KB
testcase_40 AC 902 ms
6,676 KB
testcase_41 AC 903 ms
6,676 KB
testcase_42 AC 902 ms
6,676 KB
testcase_43 AC 902 ms
6,676 KB
testcase_44 AC 902 ms
6,676 KB
testcase_45 AC 902 ms
6,676 KB
testcase_46 AC 902 ms
6,676 KB
testcase_47 AC 901 ms
6,676 KB
testcase_48 AC 902 ms
6,676 KB
testcase_49 AC 902 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

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);
  uniform_int_distribution<> rand1n(1, n - 1);
  uniform_int_distribution<> rand2n(2, 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 = rand2n(engine);
    vector<int64_t> ys(sz);
    ys[0] = rand1n(engine);
    for (int64_t i = 1; i < sz; i++) {
      ys[i] = rand1n(engine);
      while (ys[i] == ys[i - 1]) {
        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;
}
0