結果

問題 No.5020 Averaging
コンテスト
ユーザー 寝癖
提出日時 2024-02-25 16:15:41
言語 C++23
(gcc 13.3.0 + boost 1.87.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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

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/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;
}
0