結果

問題 No.5020 Averaging
コンテスト
ユーザー t33f
提出日時 2024-02-25 20:54:49
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 953 ms / 1,000 ms
コード長 4,670 bytes
コンパイル時間 1,255 ms
コンパイル使用メモリ 112,480 KB
実行使用メモリ 6,676 KB
スコア 81,366,564
最終ジャッジ日時 2024-02-25 20:55:42
合計ジャッジ時間 51,850 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <random>
#include <chrono>
#include <cmath>
#include <vector>
#include <cassert>
#include <iostream>
using namespace std;

constexpr int N = 45;
constexpr size_t Xmax = 50;
long long A[N], B[N];

#ifdef DEBUG
constexpr int timelimit = 9500;
#else
constexpr int timelimit = 950;
#endif

class Timer {
    chrono::system_clock::time_point start_time = chrono::system_clock::now();
public:
    Timer() {}
    long long get_elapsed_time() {
        auto diff = chrono::system_clock::now() - start_time;
        return chrono::duration_cast<chrono::milliseconds>(diff).count();
    }
} timer;

void write_ans(const vector<pair<int, int>> &ans, ostream &out = cout) {
    out << ans.size() << '\n';
    for (const auto &[a, b] : ans)
        out << a + 1 << ' ' << b + 1 << '\n';
}

int calc_score(const vector<pair<int, int>> &ans, bool print_result = false) {
    long long a[N], b[N];
    copy(begin(A), end(A), begin(a));
    copy(begin(B), end(B), begin(b));
    for (const auto &[i, j] : ans) {
        long long x = (a[i] + a[j]) / 2;
        long long y = (b[i] + b[j]) / 2;
        a[i] = a[j] = x;
        b[i] = b[j] = y;
    }
    if (print_result)
        for (int i = 0; i < N; ++i) cerr << a[i] << ' ' << b[i] << '\n';
    constexpr long long target = (long long)5e17;
    const long long diff = max(abs(target - a[0]), abs(target - b[0]));
    return diff > 0 ?
        int(floor(2'000'000 - 100'000 * log10(diff + 1))) :
        2'000'050 - int(ans.size());
}

struct State {
    long long a[N], b[N];
    State() {
        copy(begin(A), end(A), begin(a));
        copy(begin(B), end(B), begin(b));
    }
    State(const State &st) {
        copy(begin(st.a), end(st.a), begin(a));
        copy(begin(st.b), end(st.b), begin(b));
    }
    void apply(pair<int, int> x) { apply(x.first, x.second); }
    void apply(int i, int j) {
        const long long x = (a[i] + a[j]) / 2;
        const long long y = (b[i] + b[j]) / 2;
        a[i] = a[j] = x;
        b[i] = b[j] = y;
    }
    int get_score() const {
        constexpr long long target = (long long)5e17;
        const long long diff = max(abs(target - a[0]), abs(target - b[0]));
        return int(floor(2'000'000 - 100'000 * log10(diff + 1)));
    }
};

int calc_score(const State &initial_state, const vector<pair<int, int>> &ans) {
    State st(initial_state);
    for (const auto &[p, q] : ans) {
        st.apply(p, q);
    }
    return st.get_score();
}

int main() {
    { int n; cin >> n; assert(n == N); }
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];
    vector<pair<int, int>> ans;
    for (int i = 0; i < Xmax - N + 1; ++i) ans.emplace_back(1, 2);
    for (int i = 1; i < N; ++i) ans.emplace_back(0, i);

    int score = calc_score(ans);
    vector<pair<int, int>> best_ans = ans;
    auto best_score = score;
    mt19937 mt;
    int iter = 0;
    const auto accept = [&](int diff) {
        if (diff >= 0) {
            return true;
        } else {
            const double start_temp = 50000;
            const double end_temp = 10;
            const double progress = double(timer.get_elapsed_time()) / timelimit;
            const double f = progress * 10 - floor(progress * 10);
            const double temp = start_temp + f * (end_temp - start_temp);
            const double prob = exp(diff / temp);
            return bernoulli_distribution(prob)(mt);
        }
    };
    while (timer.get_elapsed_time() < timelimit) {
        if (mt() % 100 == 0) {
            const size_t i = mt() % 6;
            const int p = mt() % N;
            const int q = mt() % N;
            if (p == q) continue;

            iter++;
            const auto old = ans[i];
            ans[i] = {p, q};
            const auto tmp_score = calc_score(ans);
            if (accept(tmp_score - score)) {
                score = tmp_score;
            } else {
                ans[i] = old;
            }
        } else {
            const size_t i = mt() % (ans.size() - 6) + 6;
            const size_t j = mt() % (ans.size() - 6) + 6;
            if (i == j) continue;

            iter++;
            swap(ans[i], ans[j]);
            const auto tmp_score = calc_score(ans);
            if (accept(tmp_score - score)) {
                score = tmp_score;
            } else {
                swap(ans[i], ans[j]);
            }
        }

        if (best_score < score) {
            cerr << iter << " " << score << '\n';
            best_score = score;
            best_ans = ans;
        }
        if (iter % 100000 == 0) cerr << ' ' << iter << ' ' << score << endl;
    }

    cerr << "score = " << best_score << endl;
    write_ans(best_ans);
    calc_score(best_ans, true);
}
0