結果
問題 | No.2873 Kendall's Tau |
ユーザー | tnakao0123 |
提出日時 | 2024-09-09 10:39:56 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 164 ms / 4,500 ms |
コード長 | 1,951 bytes |
コンパイル時間 | 1,027 ms |
コンパイル使用メモリ | 75,608 KB |
実行使用メモリ | 7,492 KB |
最終ジャッジ日時 | 2024-09-09 10:40:02 |
合計ジャッジ時間 | 5,753 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 3 ms
6,940 KB |
testcase_07 | AC | 160 ms
7,236 KB |
testcase_08 | AC | 157 ms
7,488 KB |
testcase_09 | AC | 159 ms
7,232 KB |
testcase_10 | AC | 164 ms
7,400 KB |
testcase_11 | AC | 161 ms
7,232 KB |
testcase_12 | AC | 154 ms
7,492 KB |
testcase_13 | AC | 51 ms
6,940 KB |
testcase_14 | AC | 122 ms
6,976 KB |
testcase_15 | AC | 27 ms
6,940 KB |
testcase_16 | AC | 30 ms
6,940 KB |
testcase_17 | AC | 116 ms
6,944 KB |
testcase_18 | AC | 85 ms
6,940 KB |
testcase_19 | AC | 113 ms
6,940 KB |
testcase_20 | AC | 29 ms
6,940 KB |
testcase_21 | AC | 101 ms
6,940 KB |
testcase_22 | AC | 42 ms
6,940 KB |
testcase_23 | AC | 98 ms
6,940 KB |
testcase_24 | AC | 15 ms
6,944 KB |
testcase_25 | AC | 27 ms
6,940 KB |
testcase_26 | AC | 121 ms
6,944 KB |
testcase_27 | AC | 71 ms
6,940 KB |
testcase_28 | AC | 131 ms
6,984 KB |
testcase_29 | AC | 142 ms
7,240 KB |
testcase_30 | AC | 22 ms
6,944 KB |
testcase_31 | AC | 41 ms
6,940 KB |
testcase_32 | AC | 94 ms
6,944 KB |
ソースコード
/* -*- coding: utf-8 -*- * * 2873.cc: No.2873 Kendall's Tau - yukicoder */ #include<cstdio> #include<cmath> #include<vector> #include<algorithm> #include<utility> using namespace std; /* constant */ const int MAX_N = 200000; /* typedef */ using ll = long long; using pii = pair<int,int>; template <typename T> struct BIT { int n; vector<T> bits; BIT() {} BIT(int _n) { init(_n); } void init(int _n) { n = _n; bits.assign(n + 1, 0); } T sum(int x) { x = min(x, n); T s = 0; while (x > 0) { s += bits[x]; x -= (x & -x); } return s; } void add(int x, T v) { if (x <= 0) return; while (x <= n) { bits[x] += v; x += (x & -x); } } }; /* global variables */ int xs[MAX_N], ys[MAX_N], uys[MAX_N]; pii xys[MAX_N]; BIT<int> bit; /* subroutines */ ll calcr(int n, int xs[]) { sort(xs, xs + n); ll r = 0; for (int i = 0; i < n;) { int j = i; while (i < n && xs[j] == xs[i]) i++; r += (ll)(n - (i - j)) * (i - j); } return r / 2; } /* main */ int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d", xs + i, ys + i); copy(ys, ys + n, uys); sort(uys, uys + n); int m = unique(uys, uys + n) - uys; for (int i = 0; i < n; i++) ys[i] = lower_bound(uys, uys + m, ys[i]) - uys; for (int i = 0; i < n; i++) xys[i] = {xs[i], ys[i]}; sort(xys, xys + n); bit.init(m); ll p = 0, q = 0; for (int i = 0; i < n;) { int j = i; while (i < n && xys[j].first == xys[i].first) { auto [xi, yi] = xys[i++]; p += bit.sum(yi); q += j - bit.sum(yi + 1); } while (j < i) { auto [xj, yj] = xys[j++]; bit.add(yj + 1, 1); } } //printf(" p=%lld, q=%lld\n", p, q); ll r = calcr(n, xs); ll s = calcr(n, ys); //printf(" r=%lld, s=%lld\n", r, s); double tau = (double)(p - q) / (sqrt(r) * sqrt(s)); printf("%.10lf\n", tau); return 0; }