Submission #1196816


Source Code Expand

Copy
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> PL;
typedef long double ldouble;

int N, X, Y;

int p[200020];
int Find(int x){return p[x] == x ? x : p[x] = Find(p[x]); }
int C[200020], W[200020];
t3 P[200020];
vector <pii> E[200020];

void Uni(int x,int y){
	p[Find(x)] = Find(y);
}

const int MOD = 1e9 + 7;

ll F[200020];
ll IF[200020];
ll pw(ll x, ll y){
	ll res = 1;
	while(y){
		if(y & 1)res = res * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return res;
}

void solve(){
	scanf("%d%d%d", &N, &X, &Y);
	for(int i=1;i<=N;i++)p[i] = i;
	for(int i=1;i<=N;i++){
		scanf("%d%d", C+i, W+i);
		E[C[i]].pb(pii(W[i], i));
		P[i] = t3(W[i], C[i], i);
	}
	for(int i=1;i<=N;i++)sort(all(E[i]));
	for(int i=1;i<=N;i++){
		for(int j=1;j<sz(E[i]);j++){
			if(E[i][j].Fi + E[i][0].Fi <= X){
				Uni(E[i][j].Se, E[i][0].Se);
			}
		}
	}
	sort(P+1, P+1+N);
	int idx[3] = {};
	for(int u=0;u<3;u++){
		idx[u] = -1;
		for(int i=1;i<=N;i++){
			int ok = 1;
			rep(v, u)if(idx[v] == get<1>(P[i]))ok = 0;
			if(ok){
				idx[u] = i;
				break;
			}
		}
	}
	for(int i=1;i<=N;i++){
		int t = (int)(upper_bound(P+1, P+1+N, t3(Y - get<0>(P[i]), 1e9, 1e9)) - P - 1);
		t = min(t, i-1);
		if(t){
			rep(u, 3){
				int v = idx[u];
				if(v > t)break;
				if(get<0>(P[v]) != get<0>(P[i])){
					Uni(get<2>(P[v]), get<2>(P[i]));
				}
			}
		}
	}
	vector <int> ch[200020];
	for(int i=1;i<=N;i++){
		ch[Find(i)].pb(i);
	}
	//for(int i=1;i<=N;i++)printf("%d ", Find(i)); puts("");
	int ans = 1;
	F[0] = IF[0] = 1;
	for(int i=1;i<=N;i++)F[i] = i * F[i-1] % MOD;
	for(int i=1;i<=N;i++)IF[i] = IF[i-1] * pw(i, MOD-2) % MOD;
	for(int i=1;i<=N;i++)if(sz(ch[i])){
		map <int, int> M;
		for(int e : ch[i])M[C[e]]++;
		ll c = F[sz(ch[i])];
		for(auto e : M)c = c * IF[e.Se] % MOD;
		ans = (ll)ans * c % MOD;
	}
	printf("%d\n", ans);
}

int main(){
	int Tc = 1; // scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
}

Submission Info

Submission Time
Task D - Colorful Balls
User molamola
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2621 Byte
Status
Exec Time 192 ms
Memory 30452 KB

Compile Error

./Main.cpp: In function ‘void solve()’:
./Main.cpp:61:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &X, &Y);
                             ^
./Main.cpp:64:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", C+i, W+i);
                          ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 0 / 1000 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 138 ms 15740 KB
00_example_02.txt 5 ms 15232 KB
00_example_03.txt 5 ms 15232 KB
01.txt 6 ms 15232 KB
02.txt 5 ms 15232 KB
03.txt 10 ms 15616 KB
04.txt 6 ms 15232 KB
05.txt 7 ms 15360 KB
06.txt 6 ms 15232 KB
07.txt 80 ms 20604 KB
08.txt 6 ms 15232 KB
09.txt 40 ms 17532 KB
10.txt 28 ms 16768 KB
11.txt 6 ms 15232 KB
12.txt 6 ms 15232 KB
13.txt 11 ms 15744 KB
14.txt 5 ms 15232 KB
15.txt 39 ms 18172 KB
16.txt 74 ms 21632 KB
17.txt 16 ms 15872 KB
18.txt 33 ms 17152 KB
19.txt 66 ms 19580 KB
20.txt 170 ms 28152 KB
21.txt 164 ms 29560 KB
22.txt 151 ms 27772 KB
23.txt 190 ms 29684 KB
24.txt 148 ms 28416 KB
25.txt 168 ms 27640 KB
26.txt 185 ms 29432 KB
27.txt 148 ms 25728 KB
28.txt 192 ms 28660 KB
29.txt 180 ms 28408 KB
30.txt 144 ms 28160 KB
31.txt 190 ms 29560 KB
32.txt 158 ms 27516 KB
33.txt 190 ms 28788 KB
34.txt 175 ms 28532 KB
35.txt 135 ms 22516 KB
36.txt 149 ms 22388 KB
37.txt 136 ms 22712 KB
38.txt 133 ms 22132 KB
39.txt 135 ms 21620 KB
40.txt 181 ms 30452 KB
41.txt 166 ms 28664 KB
42.txt 170 ms 29816 KB
43.txt 151 ms 28156 KB
44.txt 187 ms 30068 KB
45.txt 150 ms 28672 KB
46.txt 166 ms 28280 KB
47.txt 126 ms 22000 KB
48.txt 131 ms 22640 KB
49.txt 128 ms 22128 KB
50.txt 116 ms 27764 KB
51.txt 110 ms 26356 KB
52.txt 119 ms 22516 KB
53.txt 118 ms 22644 KB
54.txt 118 ms 22644 KB