結果

問題 No.5020 Averaging
ユーザー 寝癖寝癖
提出日時 2024-02-25 15:57:34
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 956 ms / 1,000 ms
コード長 3,156 bytes
コンパイル時間 1,390 ms
コンパイル使用メモリ 119,044 KB
実行使用メモリ 6,676 KB
スコア 34,652,498
最終ジャッジ日時 2024-02-25 15:58:25
合計ジャッジ時間 50,353 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 908 ms
6,676 KB
testcase_01 AC 929 ms
6,676 KB
testcase_02 AC 929 ms
6,676 KB
testcase_03 AC 956 ms
6,676 KB
testcase_04 AC 930 ms
6,676 KB
testcase_05 AC 950 ms
6,676 KB
testcase_06 AC 929 ms
6,676 KB
testcase_07 AC 929 ms
6,676 KB
testcase_08 AC 906 ms
6,676 KB
testcase_09 AC 907 ms
6,676 KB
testcase_10 AC 930 ms
6,676 KB
testcase_11 AC 931 ms
6,676 KB
testcase_12 AC 906 ms
6,676 KB
testcase_13 AC 906 ms
6,676 KB
testcase_14 AC 929 ms
6,676 KB
testcase_15 AC 930 ms
6,676 KB
testcase_16 AC 930 ms
6,676 KB
testcase_17 AC 907 ms
6,676 KB
testcase_18 AC 906 ms
6,676 KB
testcase_19 AC 930 ms
6,676 KB
testcase_20 AC 930 ms
6,676 KB
testcase_21 AC 910 ms
6,676 KB
testcase_22 AC 906 ms
6,676 KB
testcase_23 AC 930 ms
6,676 KB
testcase_24 AC 930 ms
6,676 KB
testcase_25 AC 906 ms
6,676 KB
testcase_26 AC 906 ms
6,676 KB
testcase_27 AC 930 ms
6,676 KB
testcase_28 AC 934 ms
6,676 KB
testcase_29 AC 907 ms
6,676 KB
testcase_30 AC 906 ms
6,676 KB
testcase_31 AC 929 ms
6,676 KB
testcase_32 AC 930 ms
6,676 KB
testcase_33 AC 905 ms
6,676 KB
testcase_34 AC 905 ms
6,676 KB
testcase_35 AC 930 ms
6,676 KB
testcase_36 AC 930 ms
6,676 KB
testcase_37 AC 906 ms
6,676 KB
testcase_38 AC 906 ms
6,676 KB
testcase_39 AC 929 ms
6,676 KB
testcase_40 AC 929 ms
6,676 KB
testcase_41 AC 906 ms
6,676 KB
testcase_42 AC 906 ms
6,676 KB
testcase_43 AC 933 ms
6,676 KB
testcase_44 AC 930 ms
6,676 KB
testcase_45 AC 906 ms
6,676 KB
testcase_46 AC 906 ms
6,676 KB
testcase_47 AC 906 ms
6,676 KB
testcase_48 AC 930 ms
6,676 KB
testcase_49 AC 930 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

long long calc_score(const vector<pair<int, int>>& op, const vector<long long>& init_A, const vector<long long>& init_B, int N) {
    vector<long long> A = init_A, B = init_B;
    for (auto& p : op) {
        int u = p.first - 1;
        int v = p.second - 1;
        long long a = A[u], b = A[v];
        A[u] = A[v] = (a + b) / 2;
        long long c = B[u], d = B[v];
        B[u] = B[v] = (c + d) / 2;
    }
    long long V1 = abs(5e17 - A[0]);
    long long V2 = abs(5e17 - B[0]);
    long long V = max(V1, V2);
    if (V == 0) {
        return 2000050 - op.size();
    } else {
        return floor(2000000.0 - 100000.0 * log10(V + 1));
    }
}

int main() {
    srand(time(nullptr));
    
    int N;
    cin >> N;
    vector<long long> init_A(N), init_B(N);
    for (int i = 0; i < N; ++i) {
        cin >> init_A[i] >> init_B[i];
    }

    // 初期化
    int X = 50;
    vector<pair<int, int>> op;
    vector<long long> A = init_A, B = init_B;
    while (op.size() < X / 2) {
        int min_idx_A = min_element(A.begin(), A.end()) - A.begin();
        int max_idx_A = max_element(A.begin(), A.end()) - A.begin();
        if (min_idx_A == max_idx_A) break;
        op.push_back({min_idx_A + 1, max_idx_A + 1});
        long long new_value_A = (A[min_idx_A] + A[max_idx_A]) / 2;
        A[min_idx_A] = A[max_idx_A] = new_value_A;
    }

    // Bに対する操作
    while (op.size() < X) {
        int min_idx_B = min_element(B.begin(), B.end()) - B.begin();
        int max_idx_B = max_element(B.begin(), B.end()) - B.begin();
        if (min_idx_B == max_idx_B) break;
        op.push_back({min_idx_B + 1, max_idx_B + 1});
        long long new_value_B = (B[min_idx_B] + B[max_idx_B]) / 2;
        B[min_idx_B] = B[max_idx_B] = new_value_B;
    }

    // ランダムな操作を追加
    while (op.size() < X) {
        int u = rand() % N + 1;
        int v = rand() % N + 1;
        if (u != v) {
            op.push_back({u, v});
        }
    }

    long long score = calc_score(op, init_A, init_B, N);
    double start_temp = 2000.0;
    double end_temp = 10.0;
    double time_limit = 0.90;
    clock_t start_time = clock();

    while (true) {
        double now_time = double(clock() - start_time) / CLOCKS_PER_SEC;
        if (now_time > time_limit) {
            break;
        }
        vector<pair<int, int>> new_op = op;
        int idx = rand() % op.size();
        int u = rand() % (N-1) + 1;
        int v = rand() % (N-u) + u + 1;

        new_op[idx] = {u, v};
        long long new_score = calc_score(new_op, init_A, init_B, N);
        double temp = start_temp + (end_temp - start_temp) * now_time / time_limit;
        double prob = exp(min(0.0, double(new_score - score) / temp));
        if (double(rand()) / RAND_MAX < prob) {
            op = move(new_op);
            score = new_score;
        }
    }

    cout << op.size() << endl;
    for (auto& p : op) {
        cout << p.first << " " << p.second << endl;
    }

    // cout << "Score: " << score << endl;


    return 0;
}
0