#955418 (C++17) No.5020 Averaging

提出ソース

結果

問題	No.5020 Averaging
ユーザー	t33f
提出日時	2024-02-25 15:06:36
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	953 ms / 1,000 ms
コード長	4,303 bytes
コンパイル時間	1,194 ms
コンパイル使用メモリ	111,936 KB
実行使用メモリ	6,676 KB
スコア	38,118,471
最終ジャッジ日時	2024-02-25 15:07:28
合計ジャッジ時間	51,540 ms
ジャッジサーバーID （参考情報）	judge15 / judge10
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	952 ms 6,676 KB
testcase_01	AC	952 ms 6,676 KB
testcase_02	AC	952 ms 6,676 KB
testcase_03	AC	952 ms 6,676 KB
testcase_04	AC	952 ms 6,676 KB
testcase_05	AC	951 ms 6,676 KB
testcase_06	AC	952 ms 6,676 KB
testcase_07	AC	952 ms 6,676 KB
testcase_08	AC	952 ms 6,676 KB
testcase_09	AC	952 ms 6,676 KB
testcase_10	AC	953 ms 6,676 KB
testcase_11	AC	952 ms 6,676 KB
testcase_12	AC	952 ms 6,676 KB
testcase_13	AC	952 ms 6,676 KB
testcase_14	AC	952 ms 6,676 KB
testcase_15	AC	952 ms 6,676 KB
testcase_16	AC	952 ms 6,676 KB
testcase_17	AC	952 ms 6,676 KB
testcase_18	AC	952 ms 6,676 KB
testcase_19	AC	951 ms 6,676 KB
testcase_20	AC	952 ms 6,676 KB
testcase_21	AC	952 ms 6,676 KB
testcase_22	AC	952 ms 6,676 KB
testcase_23	AC	952 ms 6,676 KB
testcase_24	AC	953 ms 6,676 KB
testcase_25	AC	952 ms 6,676 KB
testcase_26	AC	952 ms 6,676 KB
testcase_27	AC	952 ms 6,676 KB
testcase_28	AC	952 ms 6,676 KB
testcase_29	AC	952 ms 6,676 KB
testcase_30	AC	952 ms 6,676 KB
testcase_31	AC	952 ms 6,676 KB
testcase_32	AC	952 ms 6,676 KB
testcase_33	AC	952 ms 6,676 KB
testcase_34	AC	952 ms 6,676 KB
testcase_35	AC	952 ms 6,676 KB
testcase_36	AC	952 ms 6,676 KB
testcase_37	AC	952 ms 6,676 KB
testcase_38	AC	952 ms 6,676 KB
testcase_39	AC	952 ms 6,676 KB
testcase_40	AC	952 ms 6,676 KB
testcase_41	AC	952 ms 6,676 KB
testcase_42	AC	951 ms 6,676 KB
testcase_43	AC	952 ms 6,676 KB
testcase_44	AC	953 ms 6,676 KB
testcase_45	AC	952 ms 6,676 KB
testcase_46	AC	952 ms 6,676 KB
testcase_47	AC	951 ms 6,676 KB
testcase_48	AC	952 ms 6,676 KB
testcase_49	AC	952 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

constexpr int N = 45;
constexpr int op_max = 50;
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;

    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 = 1000;
            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) {
        if (ans.empty() || (ans.size() < op_max && mt() % 2 == 0)) {
            const int i = int(mt() % (1 + ans.size()));
            const int p = int(mt() % N);
            const int q = int(mt() % N);
            if (p >= q) continue;

            iter++;
            ans.insert(ans.begin() + i, {p, q});
            const int tmp_score = calc_score(ans);
            if (accept(tmp_score - score)) {
                // if (tmp_score > score)
                //     cerr << iter << " " << tmp_score << '\n';
                score = tmp_score;
            } else {
                ans.erase(ans.begin() + i);
            }
        } else if (mt() % 2 == 0) {
            const size_t i = mt() % ans.size();
            const auto old = ans[i];
            const int p = int(mt() % N);
            const int q = int(mt() % N);
            if (p >= q || (old.first == p && old.second == q)) continue;

            iter++;
            ans[i] = {p, q};
            const int tmp_score = calc_score(ans);
            if (accept(tmp_score - score)) {
                // if (tmp_score > score)
                //     cerr << iter << " " << tmp_score << '\n';
                score = tmp_score;
            } else {
                ans[i] = old;
            }
        } else {
            const int i = int(mt() % ans.size());
            const auto old = ans[size_t(i)];
            ans.erase(ans.begin() + i);

            iter++;
            const int tmp_score = calc_score(ans);
            if (tmp_score >= score) {
                // if (tmp_score > score)
                //     cerr << iter << " " << tmp_score << '\n';
                score = tmp_score;
            } else {
                ans.insert(ans.begin() + i, old);
            }
        }

        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);
}

yukicoder

結果

テストケース

ソースコード