結果

問題 No.5020 Averaging
ユーザー 寝癖寝癖
提出日時 2024-02-25 16:44:53
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 961 ms / 1,000 ms
コード長 4,102 bytes
コンパイル時間 1,413 ms
コンパイル使用メモリ 121,504 KB
実行使用メモリ 6,676 KB
スコア 37,082,578
最終ジャッジ日時 2024-02-25 16:47:11
合計ジャッジ時間 51,858 ms
ジャッジサーバーID
(参考情報)
judge13 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 943 ms
6,676 KB
testcase_01 AC 937 ms
6,676 KB
testcase_02 AC 960 ms
6,676 KB
testcase_03 AC 936 ms
6,676 KB
testcase_04 AC 944 ms
6,676 KB
testcase_05 AC 936 ms
6,676 KB
testcase_06 AC 952 ms
6,676 KB
testcase_07 AC 959 ms
6,676 KB
testcase_08 AC 940 ms
6,676 KB
testcase_09 AC 953 ms
6,676 KB
testcase_10 AC 936 ms
6,676 KB
testcase_11 AC 960 ms
6,676 KB
testcase_12 AC 961 ms
6,676 KB
testcase_13 AC 936 ms
6,676 KB
testcase_14 AC 960 ms
6,676 KB
testcase_15 AC 937 ms
6,676 KB
testcase_16 AC 959 ms
6,676 KB
testcase_17 AC 959 ms
6,676 KB
testcase_18 AC 936 ms
6,676 KB
testcase_19 AC 961 ms
6,676 KB
testcase_20 AC 936 ms
6,676 KB
testcase_21 AC 960 ms
6,676 KB
testcase_22 AC 959 ms
6,676 KB
testcase_23 AC 937 ms
6,676 KB
testcase_24 AC 936 ms
6,676 KB
testcase_25 AC 942 ms
6,676 KB
testcase_26 AC 960 ms
6,676 KB
testcase_27 AC 939 ms
6,676 KB
testcase_28 AC 937 ms
6,676 KB
testcase_29 AC 937 ms
6,676 KB
testcase_30 AC 960 ms
6,676 KB
testcase_31 AC 961 ms
6,676 KB
testcase_32 AC 936 ms
6,676 KB
testcase_33 AC 960 ms
6,676 KB
testcase_34 AC 936 ms
6,676 KB
testcase_35 AC 960 ms
6,676 KB
testcase_36 AC 960 ms
6,676 KB
testcase_37 AC 936 ms
6,676 KB
testcase_38 AC 960 ms
6,676 KB
testcase_39 AC 937 ms
6,676 KB
testcase_40 AC 961 ms
6,676 KB
testcase_41 AC 960 ms
6,676 KB
testcase_42 AC 936 ms
6,676 KB
testcase_43 AC 936 ms
6,676 KB
testcase_44 AC 959 ms
6,676 KB
testcase_45 AC 961 ms
6,676 KB
testcase_46 AC 960 ms
6,676 KB
testcase_47 AC 940 ms
6,676 KB
testcase_48 AC 936 ms
6,676 KB
testcase_49 AC 941 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 = -V1/5 - V2/5;
    return V;
    // long long V = max(V1, V2);
    // if (V == 0) {
    //     return 2000050 - op.size();
    // } else {
    //     return floor(2000000.0 - 100000.0 * log10(V + 1));
    // }
}

long long calc_true_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 = 2000000.0;
    double end_temp = 1000.0;
    double time_limit = 0.93;
    clock_t start_time = clock();

    while (true) {
        double now_time = double(clock() - start_time) / CLOCKS_PER_SEC;
        if (now_time > time_limit) {
            break;
        }
        double temp = start_temp + (end_temp - start_temp) * now_time / time_limit;
        double r = double(rand()) / RAND_MAX;
        double diff_threshold = temp * log(r+1e-7);

        vector<pair<int, int>> new_op = op;
        int idx = rand() % op.size();
        if (rand() % 2 == 0) {
            int u = rand() % (N-1) + 1;
            int v = rand() % (N-u) + u + 1;
            new_op[idx] = {u, v};
        } else {
            int idx2 = rand() % op.size();
            swap(new_op[idx], new_op[idx2]);
        }
        long long new_score = calc_score(new_op, init_A, init_B, N);
        if (new_score - score > diff_threshold) {
            op = move(new_op);
            score = new_score;
        }
    }

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

    // cout << "Score: " << calc_true_score(op, init_A, init_B, N) << endl;


    return 0;
}
0