Submission #1351902

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << ", " << v.second << ">"; }

const int INF = 1 << 30;
const ll INFL = 1LL << 60;

class ModInt{
  public:
    static const ll MOD = 1000000007LL; 
    ll x;
    ModInt():x(0){};
    ModInt(ll x){
        while(x < 0) x += MOD;
        x %= MOD;
        this->x = x;
    }
    ModInt& operator += (const ModInt &l){ x += l.x; if( x >= MOD) x -= MOD; return *this; }
    ModInt& operator -= (const ModInt &l){ x -= l.x; if( x < 0 ) x += MOD; return *this; }
    ModInt& operator *= (const ModInt &l){ x = (x * l.x) % MOD; return *this; }
    ModInt operator +(const ModInt &l) const { return ModInt( x + l.x); }
    ModInt operator -(const ModInt &l) const { return ModInt( x - l.x); }
    ModInt operator *(const ModInt &l) const { return ModInt( x * l.x); }
};

// @warning rの部分はmodとってはいけない
ModInt pow(const ModInt &n, ll r){
    if(r == 0) return ModInt(1);
    ModInt ret = pow(n, r / 2);
    ret *= ret;
    if(r % 2 != 0) ret = ret * n;
    return ret;
}

// @waring nはMODと互いに素
ModInt inverse(const ModInt &n){
    return pow(n, ModInt::MOD - 2);
}

ModInt factorial(const ModInt &n){
    ll ret =1;
    for(ll i=n.x; i>1; i--){
        ret*=i;
    }
    return ModInt(ret);
}

ostream& operator << (std::ostream& os,const ModInt& a){ os << a.x; return os;}
istream& operator >> (std::istream& is,ModInt& a){ is >> a.x; return is;}

struct UnionFind{
    int n;
    vector<int> p;
    UnionFind(int nn) {
        n = nn;
        p.resize(n);
        rep(i, n) p[i] = i;
    }
    int root(int x) {
        return p[x] == x ? x : (p[x] = root(p[x]));
    }
    void unite(int x,int y) {
        x = root(x); y = root(y);
        if(x != y) p[y] = x;
    }
    bool query(int x,int y){
        return root(x) == root(y);
    }
    vector<vector<int>> get_groups() {
        vector<vector<int>> res;
        vector<bool> visited(p.size());
        rep(i, p.size()) {
            if(!visited[i]) {
                res.push_back(vector<int>());
                rep(j, p.size()) if(query(i, j)) {
                    res.back().push_back(j);
                    visited[j] = true;
                }
            }
        }
        return res;
    }
};

struct S {
    int color, weight, index;    
};
bool operator < (const S &a, const S &b) {
    return a.weight < b.weight;
}
ostream& operator << (ostream &os, const S &a) {
    return os << a.index << " c:" << a.color << " w:" << a.weight << endl;
}

class Solver {
  public:
    bool solve() {
        int N, X, Y; cin >> N >> X >> Y;
        vector<S> in(N);
        rep(i, N) cin >> in[i].color >> in[i].weight;
        sort(all(in));
        rep(i, N) in[i].index = i;
        //cerr << in << endl;
        UnionFind uf(N);
        map<int, S> lightest; // C -> W
        vector<S> lightest2; // 色の異なるボール２個
        rep(i, N) {
            int c = in[i].color, w = in[i].weight;
            //debug(c); debug(w);
            
            if(lightest.count(c) and w + lightest[c].weight <= X) {
                uf.unite(in[i].index, lightest[c].index);
            } else {
                lightest[c] = in[i];
            }
            bool same = false;
            rep(j, lightest2.size()) {
                // cerr << "cmp to " << lightest2[j].weight << endl;
                if(c != lightest2[j].color and w + lightest2[j].weight <= Y) {

                    uf.unite(in[i].index, lightest2[j].index);
                }
                if(lightest2[j].color == c) same = true;
            }
            if(lightest.size() < 2 and !same) lightest2.push_back(in[i]);
        }
        auto groups = uf.get_groups();

        ModInt ans(1);
        //debug("each group");
        for(auto &g : groups) {
            //debug(g);
            map<int, int> cnts;
            for(int i : g) cnts[in[i].color]++;
            ans *= factorial(g.size());
            for(auto p : cnts) {
                // debug(p.second);
                ans *= inverse(factorial(p.second));
            }
        }

        cout << ans << endl;
        
        return 0;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}

Submission Info

Judge Result