# AGC 12 D - Colorful Balls ( Math, Combination )

D: Colorful Balls - AtCoder Grand Contest 012 | AtCoder

1. 選擇兩個相異位置的相同顏色的球，若它們的重量和不超過 X，將它們交換位置
2. 選擇兩個相異位置的相異顏色的球，若它們的重量和不超過 Y，將它們交換位置

1≦N≦2e5
1≦X,Y≦1e9
1≦ci≦N
1≦wi≦1e9
X,Y,ci,wi はいずれも整数

O( N lg N ) / O( N )

```#TLE but a little easier to read
N, X, Y = map( int, input().split() )

C = []
W = []
for i in range( N ):
c, w = map( int, input().split() )
C.append( c - 1 )
W.append( w )

c2w = [ [] for i in range( N ) ]
for i in range( N ):
c2w[ C[ i ] ].append( W[ i ] )
for i in range( N ):
c2w[ C[ i ] ].sort()

minw, _minwp = 2e9, -1
for i in range( N ):
if len( c2w[ i ] ) == 0: continue
if minw > c2w[ i ][ 0 ]:
minw = c2w[ i ][ 0 ]
_minwp = i
minw2 = 2e9 # minimum weight of a ball with different color from minw's
for i in range( N ):
if len( c2w[ i ] ) == 0: continue
if i == _minwp: continue
if minw2 > c2w[ i ][ 0 ]:
minw2 = c2w[ i ][ 0 ]

merged = [ False for i in range( N ) ]
hi = [ 1 for i in range( N ) ]
for i in range( N ):
if len( c2w[ i ] ) == 0: continue
lb, ub = 2, len( c2w[ i ] )
while lb <= ub:
mid = lb + ub >> 1
if c2w[ i ][ 0 ] + c2w[ i ][ mid - 1 ] <= X:
hi[ i ] = max( hi[ i ], mid )
lb = mid + 1
else:
ub = mid - 1
lb, ub = 1, len( c2w[ i ] )
www = minw2 if minw != minw2 and c2w[ i ][ 0 ] == minw else minw
while lb <= ub:
mid = lb + ub >> 1
if www + c2w[ i ][ mid - 1 ] <= Y:
hi[ i ] = max( hi[ i ], mid )
merged[ i ] = True
lb = mid + 1
else:
ub = mid - 1

MOD = int( 1e9 + 7 )

fact = [ 1 ]
inv_fact = [ 1 ]
for i in range( 1, N + 1, 1 ):
fact.append( fact[ i - 1 ] * i % MOD )
inv_fact.append( pow( fact[ i ], MOD - 2, MOD ) )

ans = fact[ sum( merged[ i ] * hi[ i ] for i in range( N ) ) ]
for i in range( N ):
if not merged[ i ]: continue
ans = ans * inv_fact[ hi[ i ] ] % MOD

print( ans )
```

_

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

const int MAXN = ( int ) 2e5;

int N, X, Y;
int C[ MAXN ], W[ MAXN ];
vector< int > c2w[ MAXN ];

int cmax[ MAXN ];
int fact[ MAXN + 1 ];
int inv_fact[ MAXN + 1 ];

int int_pow( int v, int p, int m ){
int res = not ( v == 0 and p != 0 );
while( p ){
if( p & 1 ){
res = 1LL * res * v % m;
}
p >>= 1;
v = 1LL * v * v % m;
}
return res;
}

int unite[ MAXN ];

signed main(){
ios::sync_with_stdio( 0 );
{
cin >> N >> X >> Y;
for( int i = 0; i < N; ++i ){
cin >> C[ i ] >> W[ i ];
--C[ i ];
c2w[ C[ i ] ].emplace_back( W[ i ] );
}
for( int i = 0; i < N; ++i ){
sort( c2w[ i ].begin(), c2w[ i ].end() );
}
}
{
int minw = ( int ) 2e9, minwp;
for( int i = 0; i < N; ++i ){
if( c2w[ i ].empty() ) continue;
if( minw > c2w[ i ][ 0 ] ){
minw = c2w[ i ][ 0 ];
minwp = i;
}
}
int minw2 = ( int ) 2e9;
for( int i = 0; i < N; ++i ){
if( c2w[ i ].empty() ) continue;
if( i == minwp ) continue;
if( minw2 > c2w[ i ][ 0 ] ){
minw2 = c2w[ i ][ 0 ];
}
}
for( int i = 0; i < N; ++i ){
if( c2w[ i ].empty() ) continue;
{
for( int lb = 2, ub = c2w[ i ].size(); lb <= ub; ){
int mid = lb + ub >> 1;
if( c2w[ i ][ 0 ] + c2w[ i ][ mid - 1 ] <= X ){
cmax[ i ] = mid;
lb = mid + 1;
} else{
ub = mid - 1;
}
}
}
{
for( int lb = 1, ub = c2w[ i ].size(); lb <= ub; ){
int mid = lb + ub >> 1;
if( minw != minw2 and c2w[ i ][ 0 ] == minw ){
if( minw2 + c2w[ i ][ mid - 1 ] <= Y ){
unite[ i ] = mid;
lb = mid + 1;
} else{
ub = mid - 1;
}
continue;
}
if( minw + c2w[ i ][ mid - 1 ] <= Y ){
unite[ i ] = mid;
lb = mid + 1;
} else{
ub = mid - 1;
}
}
}
}
}
{
const int MOD = ( int ) 1e9 + 7;
{
for( int i = fact[ 0 ] = inv_fact[ 0 ] = 1; i <= MAXN; ++i ){
fact[ i ] = 1LL * fact[ i - 1 ] * i % MOD;
inv_fact[ i ] = int_pow( fact[ i ], MOD - 2, MOD );
}
}
int sum = 0;
for( int i = 0; i < N; ++i ){
if( not unite[ i ] ) continue;
sum += max( unite[ i ], cmax[ i ] );
}
int ans = fact[ sum ];
for( int i = 0; i < N; ++i ){
if( c2w[ i ].empty() ) continue;
if( not unite[ i ] ) continue;
ans = 1LL * ans * inv_fact[ max( unite[ i ], cmax[ i ] ) ] % MOD;
}
cout << ans << "\n";
}
return 0;
}
```