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
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 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