Submission #2107129


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=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 2488 Byte
Status WA
Exec Time 197 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
AC × 3
AC × 21
WA × 36
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 WA 6 ms 17152 KB
02.txt WA 6 ms 17152 KB
03.txt WA 10 ms 17536 KB
04.txt WA 6 ms 17152 KB
05.txt WA 7 ms 17280 KB
06.txt AC 6 ms 17152 KB
07.txt WA 62 ms 22656 KB
08.txt AC 6 ms 17152 KB
09.txt WA 29 ms 19708 KB
10.txt WA 23 ms 18688 KB
11.txt WA 6 ms 17152 KB
12.txt WA 6 ms 17152 KB
13.txt WA 10 ms 17664 KB
14.txt WA 6 ms 17152 KB
15.txt WA 32 ms 20096 KB
16.txt WA 62 ms 23808 KB
17.txt WA 14 ms 17792 KB
18.txt WA 25 ms 19072 KB
19.txt WA 47 ms 22144 KB
20.txt AC 178 ms 32632 KB
21.txt WA 159 ms 33144 KB
22.txt AC 166 ms 33532 KB
23.txt WA 163 ms 32120 KB
24.txt WA 165 ms 34176 KB
25.txt AC 164 ms 31992 KB
26.txt WA 173 ms 32888 KB
27.txt AC 177 ms 32512 KB
28.txt WA 188 ms 31932 KB
29.txt AC 197 ms 32376 KB
30.txt WA 181 ms 34432 KB
31.txt WA 183 ms 31968 KB
32.txt AC 178 ms 33020 KB
33.txt WA 187 ms 31064 KB
34.txt AC 145 ms 28792 KB
35.txt WA 84 ms 27644 KB
36.txt AC 120 ms 25204 KB
37.txt WA 86 ms 27656 KB
38.txt WA 82 ms 27168 KB
39.txt AC 91 ms 24700 KB
40.txt AC 159 ms 31224 KB
41.txt AC 159 ms 33016 KB
42.txt WA 154 ms 33912 KB
43.txt AC 153 ms 34684 KB
44.txt WA 166 ms 32632 KB
45.txt WA 148 ms 34816 KB
46.txt AC 155 ms 33016 KB
47.txt AC 82 ms 26860 KB
48.txt AC 85 ms 27500 KB
49.txt AC 83 ms 26988 KB
50.txt WA 105 ms 33396 KB
51.txt WA 109 ms 33780 KB
52.txt WA 80 ms 27380 KB
53.txt WA 80 ms 27384 KB
54.txt WA 80 ms 27380 KB