Submission #2107166
Source Code Expand
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> using namespace std; typedef long long LL; const LL mo=1e9+7; const int INF=1e9; LL fac[200001],inv[200001]; int n,x,y,fa[200001],p[200001]; vector <int> v[200001],id[200001],ans[200001]; struct data { int c,w; }a[200001]; 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; } int main() { scanf("%d%d%d",&n,&x,&y); pre(); for (int i=1;i<=n;i++) { scanf("%d%d",&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=max(x-v[i][0],y-v[p[1]][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 | 2506 Byte |
Status | WA |
Exec Time | 176 ms |
Memory | 34816 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:47: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:50:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&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 | 6 ms | 17152 KB |
00_example_02.txt | AC | 6 ms | 17152 KB |
00_example_03.txt | AC | 6 ms | 17152 KB |
01.txt | AC | 6 ms | 17152 KB |
02.txt | AC | 6 ms | 17152 KB |
03.txt | AC | 10 ms | 17536 KB |
04.txt | AC | 6 ms | 17152 KB |
05.txt | AC | 7 ms | 17280 KB |
06.txt | AC | 6 ms | 17152 KB |
07.txt | AC | 61 ms | 22304 KB |
08.txt | AC | 6 ms | 17152 KB |
09.txt | AC | 28 ms | 19200 KB |
10.txt | AC | 22 ms | 18560 KB |
11.txt | AC | 6 ms | 17152 KB |
12.txt | AC | 6 ms | 17152 KB |
13.txt | AC | 10 ms | 17664 KB |
14.txt | AC | 6 ms | 17152 KB |
15.txt | AC | 31 ms | 19968 KB |
16.txt | AC | 60 ms | 23424 KB |
17.txt | AC | 13 ms | 17792 KB |
18.txt | AC | 25 ms | 18944 KB |
19.txt | AC | 47 ms | 21248 KB |
20.txt | AC | 160 ms | 32632 KB |
21.txt | AC | 158 ms | 32632 KB |
22.txt | AC | 160 ms | 33532 KB |
23.txt | AC | 164 ms | 30952 KB |
24.txt | AC | 164 ms | 34176 KB |
25.txt | AC | 175 ms | 31992 KB |
26.txt | AC | 174 ms | 31352 KB |
27.txt | AC | 164 ms | 32512 KB |
28.txt | AC | 166 ms | 31676 KB |
29.txt | AC | 169 ms | 32376 KB |
30.txt | AC | 171 ms | 34432 KB |
31.txt | AC | 176 ms | 31032 KB |
32.txt | AC | 160 ms | 33020 KB |
33.txt | AC | 166 ms | 30928 KB |
34.txt | AC | 139 ms | 28792 KB |
35.txt | WA | 82 ms | 24948 KB |
36.txt | AC | 107 ms | 25204 KB |
37.txt | WA | 84 ms | 24960 KB |
38.txt | WA | 81 ms | 24472 KB |
39.txt | AC | 89 ms | 24700 KB |
40.txt | AC | 147 ms | 31224 KB |
41.txt | AC | 155 ms | 33016 KB |
42.txt | AC | 149 ms | 33528 KB |
43.txt | AC | 147 ms | 34684 KB |
44.txt | AC | 149 ms | 31608 KB |
45.txt | AC | 141 ms | 34816 KB |
46.txt | AC | 147 ms | 33016 KB |
47.txt | AC | 80 ms | 26860 KB |
48.txt | AC | 83 ms | 27116 KB |
49.txt | AC | 82 ms | 27116 KB |
50.txt | AC | 100 ms | 31604 KB |
51.txt | AC | 101 ms | 32628 KB |
52.txt | AC | 79 ms | 26996 KB |
53.txt | AC | 79 ms | 27000 KB |
54.txt | AC | 79 ms | 26996 KB |