結果
問題 | No.2873 Kendall's Tau |
ユーザー |
![]() |
提出日時 | 2024-09-06 22:20:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,409 bytes |
コンパイル時間 | 3,988 ms |
コンパイル使用メモリ | 267,012 KB |
最終ジャッジ日時 | 2025-02-24 04:31:13 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 WA * 17 |
ソースコード
#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 vectortemplate <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> // mintstruct 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;elsereturn nCk(n + m, n) - nCk(n + m, m + k + 1);}};#endif// #define _GLIBCXX_DEBUGint 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 * s) << endl;}