結果
問題 | No.2873 Kendall's Tau |
ユーザー | Ayuna |
提出日時 | 2024-09-07 00:34:24 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 507 ms / 4,500 ms |
コード長 | 5,416 bytes |
コンパイル時間 | 4,765 ms |
コンパイル使用メモリ | 277,312 KB |
実行使用メモリ | 29,408 KB |
最終ジャッジ日時 | 2024-09-07 00:34:38 |
合計ジャッジ時間 | 12,727 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 393 ms
21,216 KB |
testcase_08 | AC | 488 ms
26,888 KB |
testcase_09 | AC | 433 ms
20,992 KB |
testcase_10 | AC | 507 ms
29,408 KB |
testcase_11 | AC | 429 ms
20,500 KB |
testcase_12 | AC | 491 ms
26,880 KB |
testcase_13 | AC | 109 ms
9,472 KB |
testcase_14 | AC | 381 ms
24,192 KB |
testcase_15 | AC | 63 ms
7,808 KB |
testcase_16 | AC | 63 ms
7,168 KB |
testcase_17 | AC | 264 ms
17,660 KB |
testcase_18 | AC | 214 ms
15,872 KB |
testcase_19 | AC | 264 ms
18,816 KB |
testcase_20 | AC | 64 ms
8,192 KB |
testcase_21 | AC | 234 ms
15,872 KB |
testcase_22 | AC | 95 ms
10,752 KB |
testcase_23 | AC | 235 ms
16,000 KB |
testcase_24 | AC | 28 ms
6,940 KB |
testcase_25 | AC | 55 ms
7,552 KB |
testcase_26 | AC | 287 ms
16,256 KB |
testcase_27 | AC | 165 ms
14,208 KB |
testcase_28 | AC | 327 ms
23,936 KB |
testcase_29 | AC | 412 ms
26,368 KB |
testcase_30 | AC | 46 ms
6,944 KB |
testcase_31 | AC | 82 ms
8,320 KB |
testcase_32 | AC | 211 ms
16,000 KB |
ソースコード
#if 1 #include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using mint93 = modint998244353; using mint17 = modint1000000007; using mint = modint; using uint = unsigned int; using ll = long long; using ull = unsigned long long; using ld = long double; using pll = pair<ll, ll>; template <class T, class S> using p = pair<T, S>; #define edec vector template <class T> using v = vector<T>; template <class T> using vv = v<v<T>>; template <class T> using vvv = v<vv<T>>; template <class T, class S> using vp = v<p<T, S>>; using vl = v<ll>; using vvl = vv<ll>; using vvvl = vvv<ll>; using vpl = v<pll>; using vvpl = v<vpl>; constexpr ll TEN(int n) { return (n == 0) ? 1ll : 10ll * TEN(n - 1); } #define FOR(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++) #define rep(i, N) for (int i = 0; i < (int)(N); i++) #define rep1(i, N) for (int i = 1; i <= (int)(N); i++) #define rrep(i, N) for (int i = N - 1; i >= 0; i--) #define rrep1(i, N) for (int i = N; i > 0; i--) #define fore(i, a) for (auto &i : a) #define fs first #define sc second #define eb emplace_back #define pb push_back #define all(x) (x).begin(), (x).end() #define UNIQUE(x) (x).erase(unique((x).begin(), (x).end()), (x).end()); #define YES(x) cout << ((x) ? "YES" : "NO") << endl; #define Yes(x) cout << ((x) ? "Yes" : "No") << endl; #define yes(x) cout << ((x) ? "yes" : "no") << endl; #define printans(x) cout << (x == infl ? -1 : x) << endl; ll sum(vl &x) { return accumulate(all(x), 0ll); } template <class T> auto min(const T &a) { return *min_element(all(a)); } template <class T> auto max(const T &a) { return *max_element(all(a)); } template <class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } template <class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } const int inf = (1 << 29); const ll infl = (1ll << 60); const ll mod93 = 998244353ll; const ll mod17 = 1000000007ll; int popcnt(uint x) { return __builtin_popcount(x); } int popcnt(ull x) { return __builtin_popcountll(x); } int bsr(uint x) { return 32 - __builtin_clz(x); } int bsr(ull x) { return 64 - __builtin_clzll(x); } int bsf(uint x) { return __builtin_ctz(x); } int bsf(ull x) { return __builtin_ctzll(x); } ostream &operator<<(ostream &os, const mint93 &x) { return os << x.val(); } ostream &operator<<(ostream &os, const mint17 &x) { return os << x.val(); } template <class T, class S> istream &operator>>(istream &is, pair<T, S> &x) { return is >> x.fs >> x.sc; } template <class T, class S> ostream &operator<<(ostream &os, pair<T, S> &x) { return os << x.fs << " " << x.sc; } template <class T> istream &operator>>(istream &is, v<T> &x) { for (auto &y : x) is >> y; return is; } template <class T> ostream &operator<<(ostream &os, v<T> &x) { for (unsigned int i = 0, size = x.size(); i < size; i++) os << x[i] << (i == size - 1 ? "" : " "); return os; } template <class T> void print(T &t) { fore(H, t) cout << H << ' '; cout << endl; } struct StopWatch { bool f = false; clock_t st; void start() { f = true; st = clock(); } int msecs() { assert(f); return (clock() - st) * 1000 / CLOCKS_PER_SEC; } }; ll rand_int(ll l, ll r) { // [l, r] static random_device rd; static mt19937 gen(rd()); return uniform_int_distribution<ll>(l, r)(gen); } template <typename T> // mint struct Count { int N; v<T> fact, ifact; Count(int n) : N(n) { fact.resize(N + 1); ifact.resize(N + 1); fact[0] = 1; for (int i = 1; i <= N; i++) { fact[i] = fact[i - 1] * i; } ifact[N] = T(1) / fact[N]; for (int i = N; i > 0; i--) { ifact[i - 1] = ifact[i] * i; } } void extend(int n) { int pn = fact.size(); fact.resize(n + 1); ifact.resize(n + 1); for (int i = pn; i < n + 1; i++) { fact[i] = fact[i - 1] * i; } ifact[n] = T(1) / fact[n]; for (int i = n; i > pn; i--) { ifact[i - 1] = ifact[i] * i; } } T nCk(int n, int k) { if (k > n || k < 0) return 0; if (n >= int(fact.size())) extend(n); return fact[n] * ifact[k] * ifact[n - k]; } T nPk(int n, int k) { if (k > n || k < 0) return 0; if (n >= int(fact.size())) extend(n); return fact[n] * ifact[n - k]; } T nHk(int n, int k) { if (n == 0 && k == 0) return 1; return nCk(n + k - 1, k); } T catalan(int n) { return nCk(2 * n, n) - nCk(2 * n, n + 1); } T catalan(int n, int m, int k) { if (n > m + k || k < 0) return 0; else return nCk(n + m, n) - nCk(n + m, m + k + 1); } }; #endif // #define _GLIBCXX_DEBUG int main() { ll n; cin >> n; vpl xy(n); cin >> xy; sort(all(xy)); map<ll, v<int>> mp; rep(i, n){ mp[xy[i].sc].push_back(i); } v<int> yorder(n); int ymx = 0; ll s = n * (n - 1) / 2ll; fore(pa, mp) { fore(k, pa.sc){ yorder[k] = ymx; } ymx++; s -= (ll)pa.sc.size() * (pa.sc.size() - 1) / 2ll; } mp.clear(); rep(i, n){ mp[xy[i].fs].push_back(i); } ll r = n * (n - 1) / 2ll; fore(pa, mp) { r -= (ll)pa.sc.size() * (pa.sc.size() - 1) / 2ll; } ll p = 0, q = 0; fenwick_tree<ll> bit(ymx); fore(pa, mp){ fore(i, pa.sc){ p += bit.sum(0, yorder[i]); q += bit.sum(yorder[i] + 1, ymx); } fore(i, pa.sc) bit.add(yorder[i], 1); } cout << setprecision(20) << (ld)(p - q) / sqrtl(r) / sqrtl(s) << endl; }