Submission #1370496
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);
}
} else {
if (tmp.size() > 2) {
if (b[i] + b[tmp[1]] <= Y) {
g[i].pb(tmp[1]);
g[tmp[1]].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 |
1000 |
Code Size |
5123 Byte |
Status |
AC |
Exec Time |
168 ms |
Memory |
45300 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1000 / 1000 |
Status |
|
|
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 |
11 ms |
33024 KB |
00_example_02.txt |
AC |
11 ms |
33024 KB |
00_example_03.txt |
AC |
11 ms |
33024 KB |
01.txt |
AC |
11 ms |
33024 KB |
02.txt |
AC |
11 ms |
33024 KB |
03.txt |
AC |
16 ms |
33408 KB |
04.txt |
AC |
11 ms |
33024 KB |
05.txt |
AC |
13 ms |
33152 KB |
06.txt |
AC |
11 ms |
33024 KB |
07.txt |
AC |
73 ms |
37624 KB |
08.txt |
AC |
11 ms |
33024 KB |
09.txt |
AC |
46 ms |
36220 KB |
10.txt |
AC |
33 ms |
34688 KB |
11.txt |
AC |
11 ms |
33024 KB |
12.txt |
AC |
11 ms |
33024 KB |
13.txt |
AC |
16 ms |
33536 KB |
14.txt |
AC |
11 ms |
33024 KB |
15.txt |
AC |
39 ms |
35708 KB |
16.txt |
AC |
66 ms |
35580 KB |
17.txt |
AC |
21 ms |
33792 KB |
18.txt |
AC |
37 ms |
34688 KB |
19.txt |
AC |
62 ms |
36092 KB |
20.txt |
AC |
155 ms |
42488 KB |
21.txt |
AC |
148 ms |
41464 KB |
22.txt |
AC |
145 ms |
39800 KB |
23.txt |
AC |
153 ms |
44788 KB |
24.txt |
AC |
141 ms |
38776 KB |
25.txt |
AC |
157 ms |
42936 KB |
26.txt |
AC |
149 ms |
45172 KB |
27.txt |
AC |
151 ms |
41208 KB |
28.txt |
AC |
168 ms |
45172 KB |
29.txt |
AC |
159 ms |
43764 KB |
30.txt |
AC |
138 ms |
38136 KB |
31.txt |
AC |
158 ms |
45300 KB |
32.txt |
AC |
151 ms |
40824 KB |
33.txt |
AC |
161 ms |
45044 KB |
34.txt |
AC |
138 ms |
44276 KB |
35.txt |
AC |
119 ms |
41588 KB |
36.txt |
AC |
133 ms |
42244 KB |
37.txt |
AC |
120 ms |
41588 KB |
38.txt |
AC |
121 ms |
41332 KB |
39.txt |
AC |
137 ms |
41844 KB |
40.txt |
AC |
145 ms |
45172 KB |
41.txt |
AC |
152 ms |
42740 KB |
42.txt |
AC |
142 ms |
41972 KB |
43.txt |
AC |
142 ms |
40052 KB |
44.txt |
AC |
144 ms |
45300 KB |
45.txt |
AC |
135 ms |
39284 KB |
46.txt |
AC |
155 ms |
43000 KB |
47.txt |
AC |
123 ms |
40180 KB |
48.txt |
AC |
121 ms |
37108 KB |
49.txt |
AC |
123 ms |
38772 KB |
50.txt |
AC |
116 ms |
43124 KB |
51.txt |
AC |
113 ms |
41336 KB |
52.txt |
AC |
115 ms |
39420 KB |
53.txt |
AC |
116 ms |
39420 KB |
54.txt |
AC |
115 ms |
39420 KB |