Submission #1195957


Source Code Expand

// In the name of God

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <complex>

using namespace std;

#define rep(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline bool smin(T &a, const T &b)   { return a > b ? a = b : a;    }
template<typename T> inline bool smax(T &a, const T &b)   { return a < b ? a = b : a;    }

typedef long long LL;
#define int long long
const int N = (int) 1e6 + 6, mod = (int) 1e9 + 7;
vector<int> col[N];
int f[N], par[N], sz[N], inv[N];
map<int, int> c[N];
int fpm(int a, int b) { return b != 0 ? (LL) fpm((LL) a * a % mod, b >> 1) * (b & 1 ? a : 1) % mod: 1; }
pair<int, int> a[N];
int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
void unite(int u, int v) {
	u = find(u);
	v = find(v);
	if (u == v) return;
	sz[u] += sz[v];
	par[v] = u;
}
int32_t main() {
	f[0] = inv[0] = 1;
	for (int j = 1; j < N; ++j) {
		f[j] = f[j - 1] * (LL) j % mod;
		inv[j] = fpm(f[j], mod - 2);
	}
	ios_base::sync_with_stdio(0);
	int n, x, y;
	cin >> n >> x >> y;
	for (int j = 0; j < n; ++j) {
		par[j] = j;
		sz[j] = 1;
		cin >> a[j].second >> a[j].first;
	}
	sort(a, a + n);
	int cnt = 0;
	for (int j = 0; j < n; ++j) {
		col[a[j].second].push_back(j);	
		if ((j == 0 || a[j].second != a[j - 1].second) && cnt <= 100) {
			++cnt;
			for (int k = 0; k < n; ++k) if (k != j) {
				if (a[k].second == a[j].second) {
					if (a[k].first + a[j].first <= x) {
						unite(k, j);
					}
				} else {
					if (a[k].first + a[j].first <= y) {
						unite(k, j);
					}
				}
			}
		}
	}
	for (int j = 0; j < n; ++j) if ((int) col[j].size()) {
		int fst = col[j][0];
		for (int xx : col[j]) {
			if (a[fst].first + a[xx].first <= x) {
				unite(fst, xx);
			}
		}
	}
	for (int j = 0; j < n; ++j)
		c[find(j)][a[j].second]++;
	int res = 1;
	for (int j = 0; j < n; ++j)
		if (par[j] == j) {
			res = (LL) res * f[sz[j]] % mod;
			for (auto x : c[j]) {
				res = (LL) res * inv[x.second] % mod;
			}
		}
	cout << res << endl;
}



Submission Info

Submission Time
Task D - Colorful Balls
User Reyna
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2726 Byte
Status WA
Exec Time 580 ms
Memory 116608 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
AC × 3
AC × 56
WA × 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 269 ms 92928 KB
00_example_02.txt AC 269 ms 92928 KB
00_example_03.txt AC 269 ms 92928 KB
01.txt AC 269 ms 92928 KB
02.txt AC 269 ms 92928 KB
03.txt AC 279 ms 93440 KB
04.txt AC 269 ms 92928 KB
05.txt AC 272 ms 93184 KB
06.txt AC 269 ms 92928 KB
07.txt AC 391 ms 100608 KB
08.txt AC 269 ms 92928 KB
09.txt AC 341 ms 95616 KB
10.txt AC 313 ms 94976 KB
11.txt AC 269 ms 92928 KB
12.txt AC 268 ms 92928 KB
13.txt AC 278 ms 93568 KB
14.txt AC 268 ms 92928 KB
15.txt AC 327 ms 96768 KB
16.txt AC 352 ms 102144 KB
17.txt AC 290 ms 93824 KB
18.txt AC 314 ms 95616 KB
19.txt AC 361 ms 99072 KB
20.txt AC 489 ms 114432 KB
21.txt AC 479 ms 116096 KB
22.txt AC 418 ms 114816 KB
23.txt AC 561 ms 115072 KB
24.txt AC 419 ms 116096 KB
25.txt AC 484 ms 113536 KB
26.txt AC 571 ms 114816 KB
27.txt AC 387 ms 111360 KB
28.txt AC 573 ms 114816 KB
29.txt AC 535 ms 114688 KB
30.txt AC 401 ms 115968 KB
31.txt AC 580 ms 114816 KB
32.txt AC 431 ms 114176 KB
33.txt AC 569 ms 114944 KB
34.txt AC 518 ms 112896 KB
35.txt AC 433 ms 106368 KB
36.txt AC 394 ms 105344 KB
37.txt AC 436 ms 106624 KB
38.txt AC 430 ms 105984 KB
39.txt AC 361 ms 104832 KB
40.txt WA 538 ms 114560 KB
41.txt AC 486 ms 115200 KB
42.txt AC 478 ms 116608 KB
43.txt AC 417 ms 115456 KB
44.txt AC 577 ms 115968 KB
45.txt AC 417 ms 116352 KB
46.txt AC 481 ms 114560 KB
47.txt AC 329 ms 106864 KB
48.txt AC 334 ms 109680 KB
49.txt AC 331 ms 107760 KB
50.txt AC 447 ms 109812 KB
51.txt AC 359 ms 110708 KB
52.txt AC 433 ms 107636 KB
53.txt AC 434 ms 107636 KB
54.txt AC 434 ms 107636 KB