結果
問題 | No.2873 Kendall's Tau |
ユーザー | 👑 rin204 |
提出日時 | 2024-09-07 00:31:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,010 ms / 4,500 ms |
コード長 | 1,769 bytes |
コンパイル時間 | 378 ms |
コンパイル使用メモリ | 82,400 KB |
実行使用メモリ | 156,672 KB |
最終ジャッジ日時 | 2024-09-07 00:31:23 |
合計ジャッジ時間 | 18,114 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 42 ms
54,076 KB |
testcase_01 | AC | 39 ms
52,896 KB |
testcase_02 | AC | 38 ms
53,536 KB |
testcase_03 | AC | 37 ms
53,020 KB |
testcase_04 | AC | 39 ms
55,060 KB |
testcase_05 | AC | 38 ms
54,092 KB |
testcase_06 | AC | 39 ms
53,120 KB |
testcase_07 | AC | 961 ms
132,216 KB |
testcase_08 | AC | 1,010 ms
151,748 KB |
testcase_09 | AC | 977 ms
136,152 KB |
testcase_10 | AC | 994 ms
151,932 KB |
testcase_11 | AC | 1,004 ms
136,356 KB |
testcase_12 | AC | 975 ms
156,672 KB |
testcase_13 | AC | 355 ms
94,856 KB |
testcase_14 | AC | 797 ms
146,396 KB |
testcase_15 | AC | 246 ms
85,188 KB |
testcase_16 | AC | 238 ms
87,328 KB |
testcase_17 | AC | 714 ms
119,396 KB |
testcase_18 | AC | 600 ms
121,536 KB |
testcase_19 | AC | 697 ms
125,372 KB |
testcase_20 | AC | 255 ms
88,896 KB |
testcase_21 | AC | 610 ms
115,704 KB |
testcase_22 | AC | 327 ms
95,468 KB |
testcase_23 | AC | 613 ms
119,660 KB |
testcase_24 | AC | 162 ms
80,300 KB |
testcase_25 | AC | 222 ms
85,836 KB |
testcase_26 | AC | 699 ms
122,700 KB |
testcase_27 | AC | 488 ms
110,408 KB |
testcase_28 | AC | 775 ms
124,992 KB |
testcase_29 | AC | 893 ms
155,600 KB |
testcase_30 | AC | 205 ms
85,964 KB |
testcase_31 | AC | 283 ms
88,688 KB |
testcase_32 | AC | 605 ms
107,116 KB |
ソースコード
class BIT: def __init__(self, n): self.n = n self.data = [0] * (n + 1) if n == 0: self.n0 = 0 else: self.n0 = 1 << (n.bit_length() - 1) def sum_(self, i): s = 0 while i > 0: s += self.data[i] i -= i & -i return s def sum(self, l, r=-1): if r == -1: return self.sum_(l) else: return self.sum_(r) - self.sum_(l) def get(self, i): return self.sum(i, i + 1) def add(self, i, x): i += 1 while i <= self.n: self.data[i] += x i += i & -i def lower_bound(self, x): if x <= 0: return 0 i = 0 k = self.n0 while k > 0: if i + k <= self.n and self.data[i + k] < x: x -= self.data[i + k] i += k k //= 2 return i + 1 n = int(input()) xy = [list(map(int, input().split())) for _ in range(n)] xy.sort(key=lambda x: x[0]) Y_ = sorted(set(y for _, y in xy)) dic = {y: i for i, y in enumerate(Y_)} add = [] b = xy[0][0] bit = BIT(len(Y_)) p = 0 q = 0 for x, y in xy: y = dic[y] if b == x: add.append(y) else: for y_ in add: bit.add(y_, 1) add = [y] b = x p += bit.sum(y) q += bit.sum(y + 1, len(Y_)) X = [x for x, _ in xy] X.sort() r = n * (n - 1) // 2 row = 0 b = X[0] for x in X: if b == x: r -= row row += 1 else: row = 1 b = x Y = [y for _, y in xy] Y.sort() s = n * (n - 1) // 2 row = 0 b = Y[0] for y in Y: if b == y: s -= row row += 1 else: row = 1 b = y ans = (p - q) / ((r * s) ** 0.5) print(ans)