#955598 (C++23) No.5020 Averaging

提出ソース

結果

問題	No.5020 Averaging
ユーザー	寝癖
提出日時	2024-02-25 16:15:41
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	942 ms / 1,000 ms
コード長	4,101 bytes
コンパイル時間	1,772 ms
コンパイル使用メモリ	121,208 KB
実行使用メモリ	6,676 KB
スコア	38,367,331
最終ジャッジ日時	2024-02-25 16:16:39
合計ジャッジ時間	50,701 ms
ジャッジサーバーID （参考情報）	judge13 / judge10
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	907 ms 6,676 KB
testcase_01	AC	909 ms 6,676 KB
testcase_02	AC	931 ms 6,676 KB
testcase_03	AC	930 ms 6,676 KB
testcase_04	AC	942 ms 6,676 KB
testcase_05	AC	910 ms 6,676 KB
testcase_06	AC	931 ms 6,676 KB
testcase_07	AC	929 ms 6,676 KB
testcase_08	AC	905 ms 6,676 KB
testcase_09	AC	929 ms 6,676 KB
testcase_10	AC	913 ms 6,676 KB
testcase_11	AC	931 ms 6,676 KB
testcase_12	AC	906 ms 6,676 KB
testcase_13	AC	930 ms 6,676 KB
testcase_14	AC	907 ms 6,676 KB
testcase_15	AC	931 ms 6,676 KB
testcase_16	AC	906 ms 6,676 KB
testcase_17	AC	930 ms 6,676 KB
testcase_18	AC	931 ms 6,676 KB
testcase_19	AC	912 ms 6,676 KB
testcase_20	AC	908 ms 6,676 KB
testcase_21	AC	936 ms 6,676 KB
testcase_22	AC	930 ms 6,676 KB
testcase_23	AC	907 ms 6,676 KB
testcase_24	AC	924 ms 6,676 KB
testcase_25	AC	930 ms 6,676 KB
testcase_26	AC	929 ms 6,676 KB
testcase_27	AC	908 ms 6,676 KB
testcase_28	AC	932 ms 6,676 KB
testcase_29	AC	905 ms 6,676 KB
testcase_30	AC	930 ms 6,676 KB
testcase_31	AC	929 ms 6,676 KB
testcase_32	AC	909 ms 6,676 KB
testcase_33	AC	906 ms 6,676 KB
testcase_34	AC	930 ms 6,676 KB
testcase_35	AC	930 ms 6,676 KB
testcase_36	AC	907 ms 6,676 KB
testcase_37	AC	907 ms 6,676 KB
testcase_38	AC	929 ms 6,676 KB
testcase_39	AC	930 ms 6,676 KB
testcase_40	AC	907 ms 6,676 KB
testcase_41	AC	906 ms 6,676 KB
testcase_42	AC	930 ms 6,676 KB
testcase_43	AC	930 ms 6,676 KB
testcase_44	AC	907 ms 6,676 KB
testcase_45	AC	907 ms 6,676 KB
testcase_46	AC	930 ms 6,676 KB
testcase_47	AC	929 ms 6,676 KB
testcase_48	AC	931 ms 6,676 KB
testcase_49	AC	907 ms 6,676 KB

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

ソースコード

raw source code

#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/2 - V2/2;
    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 = 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;
        }
        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;
}

yukicoder

結果

テストケース

ソースコード