結果

問題 No.5020 Averaging
コンテスト
ユーザー shogo314
提出日時 2024-02-25 16:57:07
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 984 ms / 1,000 ms
コード長 4,077 bytes
コンパイル時間 2,387 ms
コンパイル使用メモリ 213,844 KB
実行使用メモリ 6,548 KB
スコア 15,445,752
最終ジャッジ日時 2024-02-25 16:58:48
合計ジャッジ時間 54,396 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using ll = long long;
using std::pair;
using std::vector;

namespace inner {
std::random_device seed_gen;
std::mt19937_64 engine(0);
template <typename T>
T randint(T l, T r) {
    assert(l <= r);
    return std::uniform_int_distribution<T>(l, r)(engine);
}
template <typename T>
T randint(T x) {
    assert(0 < x);
    return std::uniform_int_distribution<T>(0, x - 1)(engine);
}
template <typename T>
T randreal(T l, T r) {
    assert(l <= r);
    return std::uniform_real_distribution<T>(l, r)(engine);
}
template <typename T>
T randnorm(T mean, T stddev) {
    assert(stddev > 0);
    return std::normal_distribution<T>(mean, stddev)(engine);
}
template <typename T>
size_t randdist(const vector<T>& dist) {
    assert(dist.size() > 0);
    vector<T> acc(dist.size() + 1);
    for (size_t i = 0; i < dist.size(); i++) {
        assert(dist[i] >= 0);
        acc[i + 1] = acc[i] + dist[i];
    }
    assert(acc.back() > 0);
    return std::upper_bound(acc.begin(), acc.end(), randreal<T>(0, acc.back())) - acc.begin() - 1;
}
template <typename T>
void shuffle(vector<T>& v) {
    std::shuffle(v.begin(), v.end(), engine);
}
template <typename T>
T randchoice(const vector<T>& v) {
    return v[randint(v.size())];
}

auto start_time = std::chrono::system_clock::now();
/**
 * @brief ms
 */
uint64_t elapsed_time() {
    return (std::chrono::system_clock::now() - inner::start_time).count() / 1000000;
}
}  // namespace inner

struct Solver {
    static const ll ANS_MAX;
    const ll N;
    vector<ll> A;
    vector<ll> B;
    Solver(const ll& _N, const vector<ll>& _A, const vector<ll>& _B) : N(_N), A(_A), B(_B) {
    }
    pair<ll, ll> calc(const vector<pair<ll, ll>>& c) {
        assert(c.size() <= 50);
        vector<ll> tmp_A(A);
        vector<ll> tmp_B(B);
        for (auto [u, v] : c) {
            assert(0 <= u and u < N);
            assert(0 <= v and v < N);
            tmp_A.at(u) = tmp_A.at(v) = (tmp_A.at(u) + tmp_A.at(v)) / 2;
            tmp_B.at(u) = tmp_B.at(v) = (tmp_B.at(u) + tmp_B.at(v)) / 2;
        }
        return {std::abs(tmp_A[0] - 500'000'000'000'000'000), std::abs(tmp_B[0] - 500'000'000'000'000'000)};
    }
    ll max(const pair<ll, ll>& p) {
        return std::max(p.first, p.second);
    }
    vector<pair<ll, ll>> solve() {
        vector<pair<ll, ll>> best_ans(N - 1);
        for (ll i = 0; i < N - 1; i++) {
            best_ans[i] = {0, i + 1};
        }
        ll best_score = max(calc(best_ans));
        while (inner::elapsed_time() <= 680) {
            vector<pair<ll, ll>> ans(ANS_MAX);
            for (ll i = 0; i < ANS_MAX; i++) {
                ll u, v;
                do {
                    u = inner::randint(N);
                    v = inner::randint(N);
                } while (u == v or (i == ANS_MAX - 1 and u != 0 and v != 0));
                ans[i] = {u, v};
            }
            ll score = max(calc(ans));
            if (score < best_score) {
                best_ans = ans;
            }
        }
        while (inner::elapsed_time() <= 980) {
            vector<pair<ll, ll>> ans(best_ans);
            ll idx = inner::randint(N);
            auto [u, v] = [&]() -> pair<ll, ll> {
                ll u, v;
                do {
                    u = inner::randint(N);
                    v = inner::randint(N);
                } while (u == v or (idx == ANS_MAX - 1 and u != 0 and v != 0));
                return {u, v};
            }();
            ans[idx] = {u, v};
            ll score = max(calc(ans));
            if (score < best_score) {
                best_ans = ans;
            }
        }
        std::cerr << "a = " << best_score << std::endl;
        return best_ans;
    }
};
const ll Solver::ANS_MAX = 50;

int main() {
    ll N;
    std::cin >> N;
    vector<ll> A(N), B(N);
    for (int i = 0; i < N; i++) std::cin >> A[i] >> B[i];
    Solver solver(N, A, B);
    vector<pair<ll, ll>> ans = solver.solve();
    std::cout << ans.size() << std::endl;
    for (auto [u, v] : ans) {
        std::cout << u + 1 << " " << v + 1 << std::endl;
    }
}
0