結果

問題 No.5020 Averaging
コンテスト
ユーザー t33f
提出日時 2024-02-25 15:28:30
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 953 ms / 1,000 ms
コード長 2,923 bytes
コンパイル時間 1,739 ms
コンパイル使用メモリ 110,032 KB
実行使用メモリ 6,676 KB
スコア 79,893,679
最終ジャッジ日時 2024-02-25 15:29:22
合計ジャッジ時間 51,580 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

constexpr int timelimit = 950;

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) {
    cout << ans.size() << '\n';
    for (const auto &[a, b] : ans)
        cout << 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());
}


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 = 1; i < N; ++i) ans.emplace_back(0, i);

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

        iter++;
        swap(ans[i], ans[j]);
        const int 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;
    calc_score(ans, true);
    write_ans(best_ans);
}
0