結果

問題 No.5020 Averaging
ユーザー ldsyb
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
#include <queue>
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);
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0