Submission #1370497


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 i = 1;i <= n;i++) {
    if (a[i] != a[tmp[0]]) {
      if (b[i] + b[tmp[0]] <= Y) {
        g[i].pb(tmp[0]);
        g[tmp[0]].pb(i);
      }
    }
  }
  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 4966 Byte
Status WA
Exec Time 184 ms
Memory 45300 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
AC × 3
AC × 45
WA × 12
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 12 ms 33024 KB
02.txt AC 12 ms 33024 KB
03.txt AC 17 ms 33408 KB
04.txt AC 12 ms 33024 KB
05.txt AC 14 ms 33152 KB
06.txt AC 12 ms 33024 KB
07.txt WA 76 ms 37624 KB
08.txt AC 13 ms 33024 KB
09.txt WA 47 ms 36220 KB
10.txt WA 34 ms 34688 KB
11.txt AC 12 ms 33024 KB
12.txt AC 12 ms 33024 KB
13.txt AC 17 ms 33536 KB
14.txt AC 12 ms 33024 KB
15.txt AC 41 ms 35708 KB
16.txt AC 69 ms 35580 KB
17.txt AC 23 ms 33792 KB
18.txt AC 38 ms 34688 KB
19.txt WA 64 ms 36092 KB
20.txt AC 167 ms 42488 KB
21.txt AC 164 ms 41464 KB
22.txt AC 160 ms 39800 KB
23.txt AC 164 ms 44788 KB
24.txt AC 150 ms 38776 KB
25.txt AC 167 ms 42936 KB
26.txt AC 157 ms 45172 KB
27.txt AC 174 ms 41208 KB
28.txt AC 184 ms 45172 KB
29.txt AC 176 ms 43764 KB
30.txt AC 153 ms 38136 KB
31.txt AC 169 ms 45300 KB
32.txt AC 168 ms 40824 KB
33.txt AC 173 ms 45044 KB
34.txt AC 150 ms 44276 KB
35.txt WA 125 ms 41592 KB
36.txt AC 152 ms 42244 KB
37.txt WA 126 ms 41588 KB
38.txt WA 124 ms 41332 KB
39.txt AC 141 ms 41844 KB
40.txt AC 153 ms 45172 KB
41.txt AC 161 ms 42740 KB
42.txt AC 154 ms 41972 KB
43.txt AC 148 ms 40052 KB
44.txt AC 158 ms 45300 KB
45.txt AC 146 ms 39284 KB
46.txt AC 162 ms 43000 KB
47.txt AC 128 ms 40180 KB
48.txt AC 125 ms 37108 KB
49.txt AC 127 ms 38772 KB
50.txt WA 115 ms 38776 KB
51.txt WA 112 ms 37368 KB
52.txt AC 116 ms 39032 KB
53.txt WA 115 ms 39032 KB
54.txt WA 115 ms 39032 KB