Submission #2215464
Source Code Expand
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll inv[201000],fac[201000],mod=1e9+7;
int n,x,y,w1=1999999999,c1,id1,w2=1999999999,c2,id2;
struct xxx{int w,c;}d[201000]; bool used[201000];int cnt[201000],sum=0;
int h[201000],nxt[5001000],K=0,to[5001000];
void ins(int u,int v){nxt[++K]=h[u];h[u]=K;to[K]=v;}
bool cmp(xxx a,xxx b){return a.c<b.c;}
ll ksm(ll k,int p)
{
ll ans=1ll;while(p){if(p&1)ans=(ans*k)%mod;k=(k*k)%mod;p>>=1;}
return ans;
}
void init()
{
fac[0]=inv[0]=1ll;for(int i=1;i<=n;i++)fac[i]=(fac[i-1]*i)%mod;
inv[n]=ksm(fac[n],mod-2);for(int i=n-1;i>=1;i--)inv[i]=(inv[i+1]*(i+1))%mod;
}
void dfs(int x)
{
if(used[x])return;cnt[d[x].c]++;used[x]=1;sum++;
for(int i=h[x];i;i=nxt[i])dfs(to[i]);
}
int main()
{
scanf("%d%d%d",&n,&x,&y);
for(int i=1;i<=n;i++)scanf("%d%d",&d[i].c,&d[i].w);
sort(d+1,d+n+1,cmp);//for(int i=1;i<=n;i++)cout<<d[i].c<<" "<<d[i].w<<endl<<endl;
for(int i=1;i<=n;i++)
if(d[i].w<=w1){if(d[i].c!=c1)swap(w1,w2),swap(c1,c2),swap(id1,id2);w1=d[i].w;c1=d[i].c;id1=i;}
else if(d[i].w<=w2&&d[i].c!=c1){w2=d[i].w;c2=d[i].c;id2=i;}
int k;
for(int i=1;i<=n;)
{
int j=i,Min=d[i].w,col=d[i].c;k=i;
while(d[i].c==col){if(Min>d[i].w)Min=d[i].w,k=i;i++;}i=j;//cout<<Min<<" "<<i<<endl;
while(d[i].c==col){if(d[i].w+Min<=x)ins(i,k),ins(k,i);i++;}
}
for(int i=1;i<=n;i++)if(d[i].c!=c1&&d[i].w+w1<=y)ins(i,id1),ins(id1,i);
if(c2!=0)for(int i=1;i<=n;i++)if(d[i].c==c1&&d[i].w+w2<=y)ins(i,id2),ins(id2,i);
// for(int i=1;i<=n;i++,cout<<endl)for(int j=h[i];j;j=nxt[j])cout<<to[j]<<" ";
dfs(id1);init();ll ans=fac[sum];
for(int i=1;i<=n;i++)ans=(ans*inv[cnt[i]])%mod;
printf("%lld",ans);return 0;
}
//把能互相交换的处理出来,
//1.同一种颜色:把每种颜色最小的与这种颜色其他球连边 (<=x)
//2.不同种颜色:取所有球中的最小值(记颜色为c),与它不同颜色的球连边(<=y),再取一个不同于c颜色的最小值,把它与c颜色的球连边(<=y)
//3.计算答案:从2的c开始跑dfs,有被遍历到的球就把它的颜色的出现次数++,设颜色为col的球的出现次数acol,总数为sum,
//则答案可以看成从sum个位置中选a1个位置填颜色1,再从sum-a1个位置中选a2个位置填颜色2......,则ans=C(sum,a1)*C(sum-a1,a2)*C(sum-a1-a2,a3)...... =sum!/(a1!*a2!......)
Submission Info
Submission Time
2018-03-17 16:14:38+0900
Task
D - Colorful Balls
User
vjudge4
Language
C++14 (GCC 5.4.1)
Score
1000
Code Size
2362 Byte
Status
AC
Exec Time
72 ms
Memory
15104 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:29:26: 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:30:52: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++)scanf("%d%d",&d[i].c,&d[i].w);
^
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
3 ms
8448 KB
00_example_02.txt
AC
2 ms
6400 KB
00_example_03.txt
AC
3 ms
8448 KB
01.txt
AC
3 ms
8448 KB
02.txt
AC
3 ms
8448 KB
03.txt
AC
5 ms
8576 KB
04.txt
AC
3 ms
8448 KB
05.txt
AC
4 ms
8448 KB
06.txt
AC
3 ms
8448 KB
07.txt
AC
35 ms
11520 KB
08.txt
AC
3 ms
8448 KB
09.txt
AC
20 ms
9216 KB
10.txt
AC
14 ms
8832 KB
11.txt
AC
3 ms
8448 KB
12.txt
AC
3 ms
8448 KB
13.txt
AC
5 ms
8576 KB
14.txt
AC
3 ms
8448 KB
15.txt
AC
16 ms
8960 KB
16.txt
AC
34 ms
8704 KB
17.txt
AC
8 ms
8704 KB
18.txt
AC
16 ms
8832 KB
19.txt
AC
32 ms
8960 KB
20.txt
AC
70 ms
12672 KB
21.txt
AC
68 ms
9600 KB
22.txt
AC
68 ms
11904 KB
23.txt
AC
70 ms
12672 KB
24.txt
AC
67 ms
9344 KB
25.txt
AC
70 ms
12928 KB
26.txt
AC
70 ms
12416 KB
27.txt
AC
68 ms
12416 KB
28.txt
AC
72 ms
15104 KB
29.txt
AC
72 ms
15104 KB
30.txt
AC
68 ms
9088 KB
31.txt
AC
72 ms
15104 KB
32.txt
AC
70 ms
12160 KB
33.txt
AC
72 ms
15104 KB
34.txt
AC
70 ms
15104 KB
35.txt
AC
63 ms
12672 KB
36.txt
AC
69 ms
12800 KB
37.txt
AC
64 ms
12672 KB
38.txt
AC
63 ms
12672 KB
39.txt
AC
66 ms
12672 KB
40.txt
AC
68 ms
15104 KB
41.txt
AC
67 ms
12672 KB
42.txt
AC
65 ms
9600 KB
43.txt
AC
65 ms
11904 KB
44.txt
AC
67 ms
12672 KB
45.txt
AC
64 ms
9344 KB
46.txt
AC
67 ms
12928 KB
47.txt
AC
54 ms
12032 KB
48.txt
AC
54 ms
9472 KB
49.txt
AC
54 ms
9856 KB
50.txt
AC
53 ms
12032 KB
51.txt
AC
53 ms
9728 KB
52.txt
AC
55 ms
12672 KB
53.txt
AC
55 ms
12672 KB
54.txt
AC
55 ms
12672 KB