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

• 問題: No.5020 Averaging
• ユーザー: t33f
• 提出日時: 2024-02-25 15:06:36
• 言語: C++17(gcc12) (gcc 12.3.0 + boost 1.87.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

ファイルパターン	結果
other	AC * 50

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#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);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX