結果

問題 No.5020 Averaging
ユーザー square1001
提出日時 2024-02-25 17:14:33
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 1,000 ms
コード長 1,495 bytes
コンパイル時間 2,219 ms
コンパイル使用メモリ 210,572 KB
実行使用メモリ 6,676 KB
スコア 68,859,554
最終ジャッジ日時 2024-02-25 17:14:37
合計ジャッジ時間 4,147 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge10
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
int main() {
    // step #1. input
    int N;
    cin >> N;
    vector<double> A(N), B(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i];
        A[i] -= 5.0e+17;
        B[i] -= 5.0e+17;
    }
    
    // step #2. greedy
    double bestscore = 1.0e+99;
    vector<int> bestdepth;
    for (int i = 0; i < N; i++) {
        vector<int> depth(N, -1);
        depth[i] = 1;
        double x = A[i] * 0.5;
        double y = B[i] * 0.5;
        for (int j = 2; j <= N; j++) {
            double mul = pow(0.5, min(j, N - 1));
            double subbest = 1.0e+99;
            int subpos = -1;
            for (int k = 0; k < N; k++) {
                if (depth[k] == -1) {
                    double nx = x + A[k] * mul;
                    double ny = y + B[k] * mul;
                    if (subbest > max(abs(nx), abs(ny))) {
                        subbest = max(abs(nx), abs(ny));
                        subpos = k;
                    }
                }
            }
            depth[subpos] = min(j, N - 1);
            x += A[subpos] * mul;
            y += B[subpos] * mul;
        }
        if (bestscore > max(abs(x), abs(y))) {
            bestscore = max(abs(x), abs(y));
            bestdepth = depth;
        }
    }
    
    // step #3. construction
    vector<array<int, 2> > answer;
    vector<int> curdepth = bestdepth;
    while (curdepth[0] != 0) {
        int p1 = max_element(curdepth.begin(), curdepth.end()) - curdepth.begin();
        int p2 = max_element(curdepth.begin() + p1 + 1, curdepth.end()) - curdepth.begin();
        answer.push_back({p1, p2});
        curdepth[p1] -= 1;
        curdepth[p2] = -1;
    }
    
    // step #4. output
    cout << answer.size() << endl;
    for (array<int, 2> v : answer) {
        cout << v[0] + 1 << ' ' << v[1] + 1 << endl;
    }
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0