AGC 12 D - Colorful Balls ( Math, Combination )

D: Colorful Balls - AtCoder Grand Contest 012 | AtCoder

題意：
有若干個球排成一排，第 i 個球用顏色 C[ i ]，重量 W[ i ] 描述。可以進行的操作有兩種：
1. 選擇兩個相異位置的相同顏色的球，若它們的重量和不超過 X，將它們交換位置
2. 選擇兩個相異位置的相異顏色的球，若它們的重量和不超過 Y，將它們交換位置
問可以進行任意次操作的前提下，可以有幾種不同的顏色的排列方式，輸出模 1e9 + 7 後的答案

資料規模：
1≦N≦2e5
1≦X,Y≦1e9
1≦ci≦N
1≦wi≦1e9
X,Y,ci,wi はいずれも整数

解法：
首先考慮相同顏色內，和重量最小的球的重量和為 X 以內的所有球都是一群的，這裡一群指群內所有元素被允許任意進行排列。接著考慮整體重量最小的那顆球，如果它和某另一個顏色的重量第 K 小的球的重量和在 Y 以內，那麼這顆重量最小的球可以說是和高度在那另一個顏色中 K 小的一群。再一個小小觀察是只要考慮這個重量最小的球所在的群就可以了，因為若重量最小的球都無法結合，那不提更大的了。
賽中只有想到以上，漂亮的 WA 了 6% 的測資死到最後。
原因是，還必須考慮重量最小的球所屬的顏色以外的重量最小的球，因為就算重量最小的那顆球很會跟其他顏色結合，也許輸入給的 X 會很小， 導致它所在的顏色無法結合太高。這時候會形成特例，需要其他顏色的球來幫忙結合。
這就是很會救人，卻救不了自己呢。這種傢伙最容易被忘記了，要多注意呢。

時間 / 空間複雜度：
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;
}