Submission #2107155
Source Code Expand
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #define int LL using namespace std; typedef long long LL; const LL mo=1e9+7; const int INF=1e18; LL fac[500001],inv[500001]; int n,x,y,fa[500001],p[500001]; vector <int> v[500001],id[500001],ans[500001]; struct data { int c,w; }a[500001]; bool cmp(int x,int y) { int ux,vx; if (v[x].size()==0) ux=INF;else ux=v[x][0]; if (v[y].size()==0) vx=INF;else vx=v[y][0]; return ux<vx; } LL mul(LL x,LL y) { if (y==0) return 1; LL now=mul(x,y/2); now=now*now%mo; if (y%2) return now*x%mo; return now; } void pre() { fac[0]=1; for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mo; inv[n]=mul(fac[n],mo-2); for (int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mo; } int getf(int x) { if (fa[x]==x) return x; fa[x]=getf(fa[x]); return fa[x]; } void unio(int u,int v) { int fu=getf(u),fv=getf(v); if (fu==fv) return; fa[fu]=fv; } main() { scanf("%lld%lld%lld",&n,&x,&y); pre(); for (int i=1;i<=n;i++) { scanf("%lld%lld",&a[i].c,&a[i].w); v[a[i].c].push_back(a[i].w); id[a[i].c].push_back(i); } for (int i=1;i<=n;i++) sort(v[i].begin(),v[i].end()); for (int i=1;i<=n;i++) fa[i]=p[i]=i; sort(p+1,p+n+1,cmp); for (int i=1;i<=n;i++) { if (v[i].size()==0) continue; int wx=x-v[i][0]; int lx=0,rx=v[i].size()-1; while (lx<rx) { int mid=(lx+rx+1)/2; if (v[i][mid]<=wx) lx=mid; else rx=mid-1; } for (int j=0;j<lx;j++) unio(id[i][j],id[i][j+1]); } int wx=y-v[p[1]][0]; int lx=1,rx=n; while (lx<rx) { int mid=(lx+rx+1)/2; int now; if (!v[p[mid]].size()) now=INF; else now=v[p[mid]][0]; if (now<=wx) lx=mid; else rx=mid-1; } for (int i=1;i<lx;i++) unio(id[p[i]][0],id[p[i+1]][0]); for (int i=1;i<=n;i++) ans[getf(i)].push_back(a[i].c); LL ansx=1; for (int i=1;i<=n;i++) { if (getf(i)!=i) continue; sort(ans[i].begin(),ans[i].end()); ansx=ansx*fac[ans[i].size()]%mo; for (int j=0;j<ans[i].size();) { int kx=j; while (ans[i][j]==ans[i][kx]&&kx<ans[i].size()) kx++; ansx=ansx*inv[kx-j]%mo; j=kx; } } printf("%lld\n",ansx); return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Colorful Balls |
User | langsike |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2511 Byte |
Status | WA |
Exec Time | 191 ms |
Memory | 70396 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:48:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%lld%lld%lld",&n,&x,&y); ^ ./Main.cpp:51:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%lld%lld",&a[i].c,&a[i].w); ^
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | 20 ms | 43264 KB |
00_example_02.txt | AC | 14 ms | 43264 KB |
00_example_03.txt | AC | 14 ms | 43264 KB |
01.txt | WA | 14 ms | 43264 KB |
02.txt | WA | 14 ms | 43264 KB |
03.txt | WA | 20 ms | 45952 KB |
04.txt | WA | 14 ms | 43264 KB |
05.txt | WA | 16 ms | 43520 KB |
06.txt | AC | 15 ms | 43264 KB |
07.txt | WA | 78 ms | 57980 KB |
08.txt | AC | 15 ms | 43264 KB |
09.txt | WA | 39 ms | 52736 KB |
10.txt | WA | 32 ms | 49280 KB |
11.txt | WA | 14 ms | 43264 KB |
12.txt | WA | 14 ms | 43264 KB |
13.txt | WA | 19 ms | 45952 KB |
14.txt | WA | 14 ms | 43264 KB |
15.txt | WA | 42 ms | 50596 KB |
16.txt | WA | 73 ms | 59008 KB |
17.txt | WA | 23 ms | 46336 KB |
18.txt | WA | 35 ms | 49916 KB |
19.txt | WA | 58 ms | 57468 KB |
20.txt | AC | 181 ms | 68596 KB |
21.txt | WA | 174 ms | 68852 KB |
22.txt | AC | 174 ms | 69240 KB |
23.txt | WA | 190 ms | 68156 KB |
24.txt | WA | 173 ms | 69756 KB |
25.txt | AC | 176 ms | 67956 KB |
26.txt | WA | 183 ms | 68852 KB |
27.txt | AC | 180 ms | 68352 KB |
28.txt | WA | 183 ms | 68376 KB |
29.txt | AC | 178 ms | 68852 KB |
30.txt | WA | 177 ms | 70016 KB |
31.txt | WA | 191 ms | 68508 KB |
32.txt | AC | 182 ms | 68856 KB |
33.txt | WA | 190 ms | 67492 KB |
34.txt | AC | 165 ms | 66552 KB |
35.txt | WA | 94 ms | 64632 KB |
36.txt | AC | 134 ms | 63100 KB |
37.txt | WA | 97 ms | 65292 KB |
38.txt | WA | 93 ms | 64120 KB |
39.txt | AC | 103 ms | 62456 KB |
40.txt | AC | 161 ms | 68468 KB |
41.txt | AC | 163 ms | 68724 KB |
42.txt | WA | 157 ms | 69492 KB |
43.txt | AC | 162 ms | 70136 KB |
44.txt | WA | 172 ms | 68468 KB |
45.txt | WA | 159 ms | 70396 KB |
46.txt | AC | 164 ms | 68724 KB |
47.txt | AC | 96 ms | 63844 KB |
48.txt | AC | 96 ms | 64356 KB |
49.txt | AC | 94 ms | 63972 KB |
50.txt | WA | 115 ms | 69228 KB |
51.txt | WA | 115 ms | 69612 KB |
52.txt | WA | 91 ms | 64624 KB |
53.txt | WA | 91 ms | 64624 KB |
54.txt | WA | 91 ms | 64624 KB |