Submission #1370271


Source Code Expand

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

using namespace std;

template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
/** Interface */
     
inline int readChar();
template <class T = int> inline T readInt(); 
template <class T> inline void writeInt( T x, char end = 0 );
inline void writeChar( int x ); 
inline void writeWord( const char *s );
     
/** Read */
     
static const int buf_size = 4096;
     
inline int getChar() {
    static char buf[buf_size];
    static int len = 0, pos = 0;
    if (pos == len) {
        pos = 0, len = fread(buf, 1, buf_size, stdin);
    }
    if (pos == len) {
        return -1;
    }
    return buf[pos++];
}
     
inline int readChar() {
    int c = getChar();
    while (c <= 32) {
        c = getChar();
    }
    return c;
}
     
template <class T>
inline T readInt() {
    int s = 1, c = readChar();
    T x = 0;
    if (c == '-')
        s = -1, c = getChar();
    while ('0' <= c && c <= '9')
        x = x * 10 + c - '0', c = getChar();
    return s == 1 ? x : -x;
}
     
/** Write */
     
static int write_pos = 0;
static char write_buf[buf_size];
     
inline void writeChar( int x ) {
    if (write_pos == buf_size)
        fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
    write_buf[write_pos++] = x;
}
     
template <class T> 
inline void writeInt( T x, char end ) {
    if (x < 0)
        writeChar('-'), x = -x;
     
    char s[24];
    int n = 0;
    while (x || !n)
        s[n++] = '0' + x % 10, x /= 10;
    while (n--)
        writeChar(s[n]);
    if (end)
        writeChar(end);
}
     
inline void writeWord( const char *s ) {     while (*s)
writeChar(*s++); }
     
struct Flusher {
    ~Flusher() {
        if (write_pos)
            fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
    }
} flusher;


#define f first
#define s second
#define pb push_back
#define pp pop_back
#define mp make_pair
#define ll long long
#define ld double
#define ull unsigned long long
#define PI pair < int, int > 

const int N = 5e5 + 123;
const int M = 2e5;
const ld Pi = acos(-1);
const ll inf = 1e18;
const int mod = 1e9 + 7;
const int Sz = 501;
const int MOD = 1e9 + 7;

void add(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
int mult(int a, int b) {
  return 1ll * a * b % mod;
}
int sum(int a, int b) {
  add(a, b);
  return a;
}

int n, X, Y, a[N], b[N], f[N], inv[N], mn[N];
bool used[N];

int cnk(int n, int k) {
  int ans = mult(f[n], inv[k]);
  ans = mult(ans, inv[n - k]);
  return ans;
}

int bp(int a, int n) {
  int ans = 1;
  while(n) {
    if (n & 1) ans = mult(ans, a);
    a = mult(a, a);
    n >>= 1;
  }
  return ans;
}

vector < int > g[N], all, v[N];

int calc(vector < int > a) {
  sort(a.begin(), a.end());
  int n = a.size();
  int ans = 1;
  for (int i = 0;i < a.size();i++) {
    int j = i;
    while(j + 1 < a.size() && a[j + 1] == a[i]) j++;
    int cnt = j - i + 1;
    ans = mult(ans, cnk(n, cnt));
    n -= cnt;
    i = j;
  }
  return ans;
} 
void dfs(int v) {
  used[v] = 1;
  all.pb(a[v]);
  for (auto to : g[v]) if (!used[to]) dfs(to);
}
bool cmp(int i, int j) {
  return b[i] < b[j];
}
void solve() { 
  cin >> n >> X >> Y;
  f[0] = inv[0] = 1;
  for (int i = 1;i <= n;i++) {
    cin >> a[i] >> b[i];
    f[i] = mult(f[i - 1], i);
    inv[i] = bp(f[i], mod - 2);
    v[a[i]].pb(i);
  }
  vector < int > tmp;
  for (int i = 1;i <= n;i++) {
    sort(v[i].begin(), v[i].end(), &cmp);
    for (int j = 1;j < v[i].size();j++) {
      int f = v[i][j];
      int s = v[i][0];
      if (b[f] + b[s] <= X) {
        g[f].pb(s);
        g[s].pb(f);
      }
    }
    if (v[i].size()) {
      tmp.pb(v[i].front());
    }
  }
  sort(tmp.begin(), tmp.end(), &cmp);
  for (int j = 1;j < tmp.size();j++) {
    for (int i = 0;i < j;i++) {
      int f = tmp[i];
      int s = tmp[j];
      if (b[f] + b[s] <= Y) {
        g[f].pb(s);
        g[s].pb(f);
      }
    }
    continue;
    int f = tmp[0];
    int s = tmp[j];
    if (b[f] + b[s] <= Y) {
      g[f].pb(s);
      g[s].pb(f);
    }
    if (j > 1) {
      int f = tmp[1];
      int s = tmp[j];
      if (b[f] + b[s] <= Y) {
        g[f].pb(s);
        g[s].pb(f);
      }
    }
  }
  int ans = 1;
  for (int i = 1;i <= n;i++) {
    if (!used[i]) {
      all.clear();
      dfs(i);
      ans = mult(ans, calc(all));
    }
  }
  cout << ans << endl;
}

int main() {
  #ifdef wws
   freopen("in", "r", stdin);
   // freopen("in", "w", stdout);
  #endif 
  ios_base::sync_with_stdio(0);
  int tt = 1; 
  while(tt--) solve();
  return 0;
}

Submission Info

Submission Time
Task D - Colorful Balls
User SmallBoy
Language C++14 (GCC 5.4.1)
Score 0
Code Size 5292 Byte
Status WA
Exec Time 2153 ms
Memory 657916 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
AC × 3
AC × 9
WA × 19
TLE × 28
MLE × 1
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 12 ms 33024 KB
00_example_02.txt AC 12 ms 33024 KB
00_example_03.txt AC 12 ms 33024 KB
01.txt WA 13 ms 33536 KB
02.txt WA 12 ms 33024 KB
03.txt WA 117 ms 75648 KB
04.txt WA 12 ms 33024 KB
05.txt WA 32 ms 43520 KB
06.txt AC 12 ms 33024 KB
07.txt TLE 2151 ms 657916 KB
08.txt AC 13 ms 33152 KB
09.txt WA 44 ms 35456 KB
10.txt WA 556 ms 197504 KB
11.txt WA 13 ms 33280 KB
12.txt WA 12 ms 33024 KB
13.txt WA 323 ms 148224 KB
14.txt WA 12 ms 33024 KB
15.txt TLE 2150 ms 657024 KB
16.txt TLE 2148 ms 638716 KB
17.txt WA 152 ms 82816 KB
18.txt WA 151 ms 78464 KB
19.txt MLE 886 ms 264320 KB
20.txt TLE 2149 ms 642296 KB
21.txt TLE 2146 ms 625016 KB
22.txt TLE 2148 ms 634744 KB
23.txt TLE 2147 ms 629496 KB
24.txt TLE 2147 ms 625400 KB
25.txt TLE 2149 ms 646392 KB
26.txt TLE 2148 ms 625528 KB
27.txt TLE 2104 ms 41208 KB
28.txt TLE 2149 ms 642552 KB
29.txt TLE 2149 ms 640248 KB
30.txt TLE 2138 ms 506744 KB
31.txt TLE 2148 ms 636664 KB
32.txt TLE 2153 ms 638584 KB
33.txt TLE 2149 ms 643064 KB
34.txt TLE 2149 ms 643704 KB
35.txt WA 112 ms 36864 KB
36.txt TLE 2150 ms 653312 KB
37.txt WA 113 ms 37636 KB
38.txt WA 113 ms 36732 KB
39.txt AC 143 ms 50420 KB
40.txt TLE 2148 ms 636280 KB
41.txt TLE 2150 ms 637812 KB
42.txt TLE 2147 ms 628852 KB
43.txt TLE 2148 ms 632948 KB
44.txt TLE 2148 ms 629748 KB
45.txt TLE 2147 ms 629364 KB
46.txt TLE 2149 ms 640248 KB
47.txt AC 125 ms 40180 KB
48.txt AC 124 ms 37108 KB
49.txt AC 125 ms 38772 KB
50.txt TLE 2147 ms 631416 KB
51.txt TLE 2104 ms 37368 KB
52.txt WA 113 ms 38392 KB
53.txt WA 111 ms 38392 KB
54.txt WA 113 ms 38392 KB