#856884 (C++14) No.133 カードゲーム

• 問題: No.133 カードゲーム
• ユーザー: BAKATAN
• 提出日時: 2023-04-07 15:39:19
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 2 ms / 5,000 ms
• コード長: 16,791 bytes
• コンパイル時間: 2,886 ms
• コンパイル使用メモリ: 206,904 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-10-02 18:35:38
• 合計ジャッジ時間: 3,639 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	2 ms; 5,248 KB
testcase_08	AC	2 ms; 5,248 KB
testcase_09	AC	2 ms; 5,248 KB
testcase_10	AC	2 ms; 5,248 KB
testcase_11	AC	2 ms; 5,248 KB
testcase_12	AC	2 ms; 5,248 KB
testcase_13	AC	2 ms; 5,248 KB
testcase_14	AC	2 ms; 5,248 KB
testcase_15	AC	2 ms; 5,248 KB
testcase_16	AC	2 ms; 5,248 KB
testcase_17	AC	2 ms; 5,248 KB
testcase_18	AC	2 ms; 5,248 KB
testcase_19	AC	2 ms; 5,248 KB
testcase_20	AC	2 ms; 5,248 KB
testcase_21	AC	2 ms; 5,248 KB
testcase_22	AC	2 ms; 5,248 KB

ソースコード

//templateなのだ！
#include <bits/stdc++.h>
#define int long long
#define double long double
#define rep(i, l, r) for (int i=(int)(l); i<(int)(r); i++)
#define repd(i,l,r) for (int i=(int)(l); i>=r; i--)
#define all(a) (a).begin(), (a).end()
#define BS(v, k) (binary_search(all(v),(k)))
#define LBS(v, k) (lower_bound(all(v),(k))-v.begin())
#define UBS(v, k) (upper_bound(all(v),(k))-v.begin())
using namespace std;
using vec=vector<int>;
using mat=vector<vec>;
using graph=vector<vector<pair<int, int> > >;
#define cinvec(v) \
    rep(bakatan,0,(int)v.size()) cin>>v[bakatan];
#define coutvec(v) \
    rep(bakatan,0,(int)v.size()) cout<<v[bakatan]<<' '; cout<<endl;
#define coutvecl(v) \
    rep(bakatan,0,(int)v.size()) cout<<v[bakatan]<<endl;
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
const int INT_INF=(1ll<<31)-1;
const int INF=1e17;
const int mod1=998244353ll;
const int mod2=1e9+7;
//数学系関数なのだ！
int GCD(int a, int b) {
    if (a<0) a=abs(a); 
    if (b<0) b=abs(b);
    if (a<b) swap(a,b);
    if (b==0) return a;
    else return GCD(b,a%b);
}
int LCM(int a, int b) {
    return (a/GCD(a,b))*b;
}
int Pow(int a, int b) {
    int Ans=1;
    rep(i,0,b) Ans*=a;
    return Ans;
}
int Powmod (int a, int b, int m) {
    int Ans=1, p=a;
    rep(i, 0, 63) {
        if ((b&(1ll<<i))!=0) {Ans*=p; Ans%=m;}
        p*=p; p%=m;
    }
    return Ans;
}
int extGCD(int a, int b, int &x, int &y) {
    if (a<b) return extGCD(b, a, y, x);
    if (b==0) {x=1,y=0; return a;}
    int d=extGCD(b,a%b,y,x); y-=a/b*x;
    return d;
} 
void Euclid(int a, int b, int c, int &x, int &y) {
    int d=extGCD(a,b,x,y); x*=c/d, y*=c/d;
}
int Digit(int N) {
    int Ans=0;
    while (N>0) {N/=10; Ans++;}
    return Ans;
}
int DigitSum(int N) {
    int Ans=0;
    while (N>0) {Ans+=N%10; N/=10;}
    return Ans;
}
int MOD(int a, int m) {
    return (a%m+m)%m;
}
int CRT(int b1, int m1, int b2, int m2) {
    int p, q; int d=extGCD(m1, m2, p, q);
    if ((b2-b1)%d!=0) return -1;
    return MOD(b1+m1*((b2-b1)/d*p%(m2/d)), m1*m2/d);
}
void primefac(int N,vec &p,vec &e) {
    for (int i=2;i*i<=N;i++) {
        int cnt=0; while (N%i==0) {N/=i; cnt++;}
        if (cnt>0) {p.push_back(i); e.push_back(cnt);}
    }
    if (N!=1) {p.push_back(N); e.push_back(1);}
    return;
}
void getprime(int N, vector<int> &prime) {
    vector<bool> flag(N+1, true);
    for (int i=2; i*i<=N; i++) {
        if (flag[i]) {for (int j=2; i*j<=N; j++) flag[i*j]=false;}
    }
    rep(i, 2, N+1) {if (flag[i]) prime.push_back(i);}
    return;
}
// sum_{i=0}^{N-1} floor((A*i+B)/M)
int floorsum(int N,int M,int A,int B) {
    if (N==0) return 0;
    int Ans=0;
    if (A>=M) Ans+=N*(N-1)*(A/M)/2,A%=M;
    if (B>=M) Ans+=N*(B/M),B%=M;
    int Y=(A*N+B)/M,X=Y*M-B;
    if (A==0||Y==0) return Ans;
    Ans+=(N-(X+A-1)/A)*Y+floorsum(Y,A,M,(A-X%A)%A);
    return Ans;
}
//n以下の正整数のうちnと互いに素なものの個数...O(sqrt(N))
int Euler(int n) {
    int Ans=n; vec p; //素因数
    for (int i=2;i*i<=n;i++) {
        if (n%i==0) {
            p.push_back(i);
            while (n%i==0) {n/=i;}
        }
    }
    if (n!=1) p.push_back(n);
    rep(i,0,(int)p.size()) Ans=Ans/p[i]*(p[i]-1);
    return Ans;
}
vec fact,fact_inv,inv;
void init_nCk(int SIZE,int mod) {
    fact.resize(SIZE+5); fact_inv.resize(SIZE+5); inv.resize(SIZE+5);
    fact[0]=fact[1]=1; fact_inv[0]=fact_inv[1]=1; inv[1]=1;
    rep(i,2,SIZE+5) {
        fact[i]=fact[i-1]*i%mod;
        inv[i]=mod-inv[mod%i]*(mod/i)%mod;
        fact_inv[i]=fact_inv[i-1]*inv[i]%mod;
    }
}
int nCk(int n,int k,int mod) {
    if (n<k||n<0||k<0) return -1;
    return fact[n]*(fact_inv[k]*fact_inv[n-k]%mod)%mod;
}
//データ構造なのだ！
/* unionfindの説明なのだ！
unionfind():大きさ0で宣言...O(1)
unionfind(N):大きさNで宣言...O(1)
init(N):大きさNで初期化
root(v):頂点vの根..O(1)
unite(u,v):頂点uを含む集合と頂点vを含む集合を統合
same(u,v):頂点uとvが同じ集合に属するか判定
*/
class UnionFind {
    public:
    vector<int> par, siz;
    UnionFind() {init(0);}
    UnionFind(int N) {init(N);}
    void init(int N) {par.resize(N,-1); siz.resize(N,1);}
    int root(int pos) { //posの根を返す関数
        if (par[pos]==-1) return pos;
        else return par[pos]=root(par[pos]);
    }
    void unite(int u, int v) { //要素uとvを統合する関数
        int RootU=root(u), RootV=root(v);
        if (RootU==RootV) return;
        if (siz[RootU]<siz[RootV]) {par[RootU]=RootV; siz[RootV]+=siz[RootU];}
        else {par[RootV]= RootU; siz[RootU]+=siz[RootV];}
    }
    bool same(int u, int v) { //要素uとvが同じグループに属するか判定する関数
        if (root(u)==root(v)) return true;
        else return false;
    }
};
/* セグメント木の説明なのだ！
・宣言 : N=配列の大きさ, fx=モノイドXの二項演算, ex=fx(a,e)=fx(e,a)=aとなる単位元e
・set(i,x):i番目をxとおく（後でbuild()が必要）...O(logN)
・build():セグメント木を再構築する...O(1)
・update(i,x):i番目をxに変更する...O(logN)
・query(l,r):fx(A[l],A[l+1],...A[r-1])を求める...O(logN)
・find_right, find_left:セグメント木上での二分探索（必要に応じて）...0(logN)
*/
template <typename X> 
struct SegmentTree{
    using FX=function<X(X,X)>;
    vector<X> dat; //各ノードの値
    int siz; //葉の数
    FX fx; //二項演算
    const X ex; //単位元
    SegmentTree(int N,FX fx_,X ex_):siz(),fx(fx_),ex(ex_),dat() {
        siz=1; while (siz<N) siz*=2;
        dat.resize(2*siz-1); rep(i,0,2*siz-1) dat[i]=ex;
    }
    void set(int i,X x) { dat[i+siz-1] = x;}
    void build() {
        for (int i=siz-2; i>=0; i--) dat[i]=fx(dat[2*i+1], dat[2*i+2]);
    }
    void update(int pos,X x) {
        pos+=siz-1; dat[pos] = x;
        while (pos>0) {pos=(pos-1)/2; dat[pos]=fx(dat[pos*2+1], dat[pos*2+2]);}
    }
    X query(int a,int b) {return query_sub(a,b,0,0,siz);} //範囲は[a, b)
    X query_sub(int a,int b,int k,int l,int r) {
        if (r<=a||b<=l) return ex;
        if (a<=l&&r<=b) return dat[k];
        X left=query_sub(a,b,k*2+1,l,(l+r)/2);
        X right=query_sub(a,b,k*2+2,(l+r)/2,r);
        return fx(left, right);
    }
};
//セグ木の二項演算
int Fx(int x1, int x2) {return min(x1,x2);}
int Fx2(int x1,int x2) {return max(x1,x2);}
/*遅延評価セグメント木の説明なのだ！
SegTreeLazy(n,fx,fa,fm,ex,em):要素数n,二項演算fx,fa,fm,単位元ex,emのセグ木を構築...O(logn)
set(i,x)→build():i番目の値をxになおす...set:O(1),build:O(logn)
update(a,b,x):[a,b)の値をxに変更...O(logn)
query(a,b):[a,b)に対応するなんらかの値を返す...O(logn)
*/
template<typename X,typename M> 
struct SegTreeLazy {
    using FX=function<X(X,X)>; FX fx; //セグ木のデータに関する演算
    using FA=function<X(X,M)>; FA fa;//遅延評価を作用させる演算
    using FM=function<M(M,M)>; FM fm; //遅延評価に関する演算
    int n;
    const X ex; const M em; //集合X,Mに関する単位元
    vector<X> dat;
    vector<M> lazy;
    SegTreeLazy(int n_,FX fx_,FA fa_,FM fm_,X ex_,M em_)
    :n(),fx(fx_),fa(fa_),fm(fm_),ex(ex_),em(em_),dat(n_*4,ex),lazy(n_*4,em) {
        n=1; while (n_>n) n*=2;
    }
    void set(int i,X x) {dat[i+n-1]=x;}
    void build() {
        for (int k=n-2;k>=0;k--) dat[k]=fx(dat[2*k+1],dat[2*k+2]);
    }
    void eval(int k) {
        if (lazy[k]==em) return;
        if (k<n-1) {
            lazy[2*k+1]=fm(lazy[2*k+1],lazy[k]);
            lazy[2*k+2]=fm(lazy[2*k+2],lazy[k]);
        }
        dat[k]=fa(dat[k],lazy[k]);
        lazy[k]=em;
    }
    void update(int a,int b,M x,int k,int l,int r) {
        eval(k);
        if (a<=l&&r<=b) {
            lazy[k]=fm(lazy[k],x); eval(k);
        }
        else if (a<r&&l<b) {
            update(a,b,x,2*k+1,l,(l+r)/2);
            update(a,b,x,2*k+2,(l+r)/2,r);
            dat[k]=fx(dat[2*k+1],dat[2*k+2]);
        }
    }
    void update(int a,int b,M x) {update(a,b,x,0,0,n);}
    X query_sub(int a,int b,int k,int l,int r) {
        eval(k);
        if (r<=a||b<=l) return ex;
        if (a<=l&&r<=b) return dat[k];
        else {
            X left=query_sub(a,b,2*k+1,l,(l+r)/2);
            X right=query_sub(a,b,2*k+2,(l+r)/2,r);
            return fx(left,right);
        }
    }
    X query(int a,int b) {return query_sub(a,b,0,0,n);}
};
//遅延セグ木の二項演算
int fx(int a,int b) {return min(a,b);}
int fa(int a,int b) {return b;}
int fm(int a,int b) {return b;}
/* BITの説明なのだ！
宣言:N=配列の大きさ
add(l,r,x):[l,r)にxを加算する
query(l,r):[l,r)の和を返す
＊内部では1-indexになっていることに注意
*/
template <typename T>
struct BIT {
    int N; vector<T> bit[2];
    BIT(int n) {init(n);}
    private:
    void init(int n) {
        N=n+1; rep(i,0,2) bit[i].assign(N,0);
    }
    void add_sub(int p,int i,T x) {
        for (int idx=i; idx<N; idx+=(idx&-idx)) bit[p][idx]+=x;
    }
    T sum_sub(int p,int i) {
        T s(0);
        for (int idx=i; idx>0; idx-=(idx&-idx)) s+=bit[p][idx];
        return s;
    }
    T sum(int i) {return sum_sub(0,i)+sum_sub(1,i)*i;}
    public:
    void add(int l,int r,T x) {
        l++; r++;
        add_sub(0,l,-x*(l-1)); add_sub(0,r,x*(r-1));
        add_sub(1,l,x); add_sub(1,r,-x);
    }
    T query(int l,int r) {l++; r++; return sum(r-1)-sum(l-1);}
};
/* RollingHashの説明なのだ！
宣言:Sに関するHash値を計算する
query(l,r):[l,r)のHash値を計算する
*/
struct RollingHash{
    int Mod=(1ll<<61)-1,Modsub=(1ll<<31)-1;
    int RollingHash_MOD(int x) { 
        int res=(x>>61)+(x&Mod);
        if (res>=Mod) res-=Mod;
        return res;
    }
    int Mul(int a,int b) {
        int tmp=(a&Modsub)*(b>>31)+(b&Modsub)*(a>>31);
        int res=(a>>31)*(b>>31)*2+(tmp>>30)+((tmp&((1ll<<30)-1))<<31)+(a&Modsub)*(b&Modsub);
        return RollingHash_MOD(res);
    }
    string S; int siz,Base=RollingHash_MOD(rand());
    vec Hash, Power;
    RollingHash(string T):S(T),siz((int)T.size()) {
        Hash.resize(siz+1); Power.resize(siz+1); Hash[0]=0; Power[0]=1;
        rep(i,1,siz+1) Hash[i]=RollingHash_MOD(Mul(Base,Hash[i-1])+(S[i-1]-'a')+1);
        rep(i,1,siz+1) Power[i]=Mul(Power[i-1],Base);
    }
    int query(int l, int r) {
        return RollingHash_MOD(Hash[r]+Mod-Mul(Hash[l],Power[r-l]));
    }
};
//グラフアルゴリズムなのだ！
void BFS(int start, mat G, vec &dist) {
    int N=(int)G.size(); 
    dist.assign(N,-1); dist[start]=0;
    queue<int> Q; Q.push(start);
    while (!Q.empty()) {
        int pos=Q.front(); Q.pop();
        rep(i,0,(int)G[pos].size()) {
            if (dist[G[pos][i]]==-1) {
                dist[G[pos][i]]=dist[pos]+1; Q.push(G[pos][i]);
            }
        }
    }
    return;
}
void Dijkstra(int start, graph G, vector<int> &dist) {
    int N=(int)G.size(); 
    dist.resize(N); rep(i,0,N) dist[i]=INF;
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > Q;
    vector<bool> flag(N, false);
    dist[start]=0; Q.push(make_pair(0,start));
    while (!Q.empty()) {
        int pos=Q.top().second; Q.pop();
        if (flag[pos]) continue;
        flag[pos]=true;
        rep(i,0,(int)G[pos].size()) {
            if (dist[G[pos][i].first]>dist[pos]+G[pos][i].second) {
                dist[G[pos][i].first]=dist[pos]+G[pos][i].second;
                Q.push(make_pair(dist[G[pos][i].first], G[pos][i].first));
            }
        }
    }
}
int Path2(int s, int t, graph G, vector<int> &route) {
    int N=(int)G.size(), pos=t; 
    vector<int> dist(N); Dijkstra(s, G, dist);
    while (true) {
        route.push_back(pos);
        if (pos==s) break;
        rep(i,0,(int)G[pos].size()) {
            if (dist[G[pos][i].first]+G[pos][i].second==dist[pos]) {
                pos=G[pos][i].first; break;
            }
        }
    }
    reverse(all(route));
    return dist[t];
}
//トポロジカルソート
vec topo_sort(mat G) { //BFS
    int N=(int)G.size(); vec Ans,ind(N);
    rep(i,0,N) {
        rep(j,0,(int)G[i].size()) ind[G[i][j]]++;
    }
    queue<int> Q;
    rep(i,0,N) {
        if (ind[i]==0) Q.push(i);
    }
    while (!Q.empty()) {
        int pos=Q.front(); Q.pop();
        Ans.push_back(pos);
        rep(i,0,(int)G[pos].size()) {
            ind[G[pos][i]]--;
            if (ind[G[pos][i]]==0) Q.push(G[pos][i]);
        }
    }
    return Ans;
}
/*最大フローの説明なのだ！
宣言:N=グラフの大きさ
add(a,b,c):aからbをつなぐ大きさcの辺を追加する(0-index、有向辺)
max_flow(s,t):sからtへの最大フローを求める
*/
struct MaxFlow_Edge {int to,cap,rev;};
class MaxFlow {
    public:
    int N; vector<bool> flag; vector<vector<MaxFlow_Edge> > G;
    MaxFlow(int n):N(n),flag(n),G(n) {}
    void add(int a,int b,int c) {
        MaxFlow_Edge tmp1={b,c,(int)G[b].size()};
        MaxFlow_Edge tmp2={a,0,(int)G[a].size()};
        G[a].push_back(tmp1); G[b].push_back(tmp2);
    }
    int dfs(int pos,int goal,int MinFlow) {
        if (pos==goal) return MinFlow;
        flag[pos]=true;
        rep(i,0,(int)G[pos].size()) {
            if (G[pos][i].cap==0) continue;
            if (flag[G[pos][i].to]) continue;
            int Flow=dfs(G[pos][i].to,goal,min(MinFlow,G[pos][i].cap));
            if (Flow>0) {
                G[pos][i].cap-=Flow; 
                G[G[pos][i].to][G[pos][i].rev].cap+=Flow;
                return Flow;
            }
        }
        return 0;
    }
    int max_flow(int s,int t) {
        int Ans=0;
        while (true) {
            rep(i,0,N) flag[i]=false;
            int Flow=dfs(s,t,INF);
            if (Flow==0) break;
            Ans+=Flow;
        }
        return Ans;
    }
};
/*LCAの説明なのだ！
LCA(mat G,int root):根がrootの木Gで前処理を行う...O(NlogN)
query(u,v):頂点uとvの最小共通祖先を求める...O((logN)^2)
*/
struct LCA{
    mat par; //par[k][v]:頂点vの2^k先の親
    vec dist;
    LCA(const mat &G,int root=0) {init(G,root);}
    void init(const mat &G,int root=0) {
        int N=(int)G.size(),cnt=0;
        while ((1<<cnt)<N) cnt++;
        par.assign(cnt,vec(N,-1));
        dist.assign(N,-1);
        dfs(G,root,-1,0);
        rep(k,0,cnt-1) {
            rep(v,0,N) {
                if (par[k][v]<0) par[k+1][v]=-1;
                else par[k+1][v]=par[k][par[k][v]];
            }
        }
    }
    void dfs(const mat &G,int v,int p,int d) {
        par[0][v]=p; dist[v]=d;
        rep(i,0,(int)G[v].size()) {
            if (G[v][i]!=p) dfs(G,G[v][i],v,d+1);
        }
    }
    int query(int u,int v) {
        if (dist[u]<dist[v]) swap(u,v);
        int cnt=(int)par.size();
        rep(k,0,cnt) {
            if ((dist[u]-dist[v])>>k&1) u=par[k][u];
        }
        if (u==v) return u;
        for (int k=cnt-1;k>=0;k--) {
            if (par[k][u]!=par[k][v]) {u=par[k][u]; v=par[k][v];}
        }
        return par[0][u];
    }
};
//便利関数なのだ！
template <typename T>
void chmax(T &a, const T b) {
    if (a<b) a=b;
}
template <typename T>
void chmin(T &a, const T b) {
    if (a>b) a=b;
}
int swap_count(vec A) { //i<j,A[i]>A[j]を満たす(i,j)を数える...O(NlogN)
    int N=(int)A.size();
    //まず座圧
    set<int> T; rep(i,0,N) T.insert(A[i]);
    vec t; while (!T.empty()) {t.push_back(*begin(T)); T.erase(*begin(T));}
    vec P(N); rep(i,0,N) P[i]=LBS(t,A[i]);
    //最大がN-1になったから転倒数を求める
    BIT<int> S(N);
    int Ans=0;
    rep(i,0,N) {
        Ans+=i-S.query(0,P[i]);
        S.add(P[i],P[i]+1,1);
    }
    return Ans;
}
template <typename T>
T Sum(vector<T> A) {
    T Ans=0;
    rep(i,0,(int)A.size()) Ans+=A[i];
    return Ans;
}
template<typename T>
T Min(vector<T> A) {
    T Ans=A[0];
    rep(i,1,(int)A.size()) chmin(Ans,A[i]);
    return Ans;
}
template<typename T>
T Max(vector<T> A) {
    T Ans=A[0];
    rep(i,1,(int)A.size()) chmax(Ans,A[i]);
    return Ans;
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    //init_nCk(2*1e6+9,mod2);
    cout<<fixed<<setprecision(15);
    srand(time(NULL));
    int N; cin>>N;
    vec A(N),B(N); cinvec(A); cinvec(B);
    double p=0,q=0;
    vec x(N),y(N); rep(i,0,N) {x[i]=i; y[i]=i;}
    do {
        do {
            int a=0,b=0;
            rep(i,0,N) {
                if (A[x[i]]>B[y[i]]) a++;
                if (A[x[i]]<B[y[i]]) b++;
            }
            if (a>b) p++;
            q++;
        } while (next_permutation(all(y)));
    } while (next_permutation(all(x)));
    cout<<(double)(p/q)<<endl;
}