結果

問題 No.2873 Kendall's Tau
ユーザー Tatsu_mrTatsu_mr
提出日時 2024-09-06 23:28:28
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,538 bytes
コンパイル時間 5,969 ms
コンパイル使用メモリ 325,200 KB
実行使用メモリ 29,780 KB
最終ジャッジ日時 2024-09-06 23:29:05
合計ジャッジ時間 16,006 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 WA -
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;

template <class T>
struct Compression {
    vector<T> a;
    
    Compression(vector<T> a_) : a(a_) {
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());
    }
    
    int size() {
        return (int)a.size();
    }
    
    T val(int p) {
        return a[p];
    }
    
    int idx(T x) {
        int res = lower_bound(a.begin(), a.end(), x) - a.begin();
        return res;
    }
};

using lint = long long;
using ld = long double;;

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> ps;
    vector<int> ys;
    map<int, lint> mpx, mpy;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        ps.emplace_back(x, y);
        ys.emplace_back(y);
        mpx[x]++;
        mpy[y]++;
    }
    sort(ps.begin(), ps.end());
    Compression cy(ys);
    atcoder::fenwick_tree<lint> fw(cy.size());
    lint p = 0, q = 0, r = 0, s = 0;
    for (int i = 0; i < n; i++) {
        auto [x, y] = ps[i];
        fw.add(cy.idx(y), 1LL);
        if (i > 0 && ps[i - 1].first == x) {
            continue;
        }
        p += fw.sum(0, cy.idx(y));
        q += fw.sum(cy.idx(y) + 1, cy.size());
    }
    r = s = (lint)n * (lint)(n - 1) / 2LL;
    for (auto [key, val] : mpx) {
        r -= val * (val - 1LL) / 2LL;
    }
    for (auto [key, val] : mpy) {
        s -= val * (val - 1LL) / 2LL;
    }
    cout << fixed << setprecision(10);
    cout << ((ld)p - (ld)q) / sqrtl((ld)r * (ld)s) << endl;
}
0