oj.uz

Submission #13271

# Submission time Handle Problem Language Result Execution time Memory
13271 2015-02-09T07:06:47 Z dohyun0324 Energetic turtle (IZhO11_turtle) C++
15 / 100
 102 ms 1876 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int x,y,n,m,k,t,z,prime[30010],top,ch[300010];
ll d[21][21],d2[21][21],dis[21][21],arr[30010],dap;
struct data{
    int x,y;
    bool operator<(const data&r)const{
        if(x==r.x) return y<r.y;
        return x<r.x;
    }
}a[300010];
ll cnt(int x,int p)
{
    ll c=0;
    while(x){x/=p; c+=x;}
    return c;
}
ll comb(int x,int y)
{
    int i,j;
    ll ans=1;
    for(i=1;i<=top;i++){
        arr[i]=cnt(x,prime[i])-cnt(y,prime[i])-cnt(x-y,prime[i]);
        for(j=1;j<=arr[i];j++){ans*=prime[i]; ans%=z;}
    }
    return ans;
}
int main()
{
    int i,j,r;
    scanf("%d %d %d %d %d",&n,&m,&k,&t,&z);
    for(i=1;i<=k;i++) scanf("%d %d",&a[i].x,&a[i].y); k+=2;
    a[k].x=n; a[k].y=m;
    for(i=2;i<=300000;i++){
        if(ch[i]==1) continue;
        for(j=i;j<=300000;j+=i) ch[j]=1;
        prime[++top]=i;
    }
    sort(a+1,a+k+1);
    for(i=1;i<=k;i++){
        for(j=i+1;j<=k;j++){
            if(a[j].y>=a[i].y) dis[i][j]=comb(a[j].x-a[i].x+a[j].y-a[i].y,a[j].y-a[i].y);
        }
    }
    for(i=1;i<=k;i++){
        for(j=i+1;j<=k;j++){
            d[i][j]=dis[i][j];
            for(r=i+1;r<=j;r++){
                d[i][j]-=d[i][r]*dis[r][j];
                if(d[i][j]<0) d[i][j]+=z;
            }
        }
    }
    t++; d2[1][0]=1;
    for(i=2;i<=k;i++){
        for(j=1;j<=t;j++){
            for(r=1;r<=i-1;r++){
                d2[i][j]+=d2[r][j-1]*d[r][i];
                d2[i][j]%=z;
            }
        }
    }
    for(i=1;i<=t;i++){dap+=d2[k][i]; dap%=z;}
    printf("%lld",dap);
    return 0;
}

Compilation message

turtle.cpp: In function 'int main()':
turtle.cpp:34:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(i=1;i<=k;i++) scanf("%d %d",&a[i].x,&a[i].y); k+=2;
     ^~~
turtle.cpp:34:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(i=1;i<=k;i++) scanf("%d %d",&a[i].x,&a[i].y); k+=2;
                                                       ^
turtle.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d %d",&n,&m,&k,&t,&z);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
turtle.cpp:34:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=k;i++) scanf("%d %d",&a[i].x,&a[i].y); k+=2;
                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1756 KB Output is correct
2 Correct 13 ms 1840 KB Output is correct
3 Correct 11 ms 1784 KB Output is correct
4 Incorrect 34 ms 1784 KB Output isn't correct
5 Incorrect 51 ms 1784 KB Output isn't correct
6 Incorrect 32 ms 1788 KB Output isn't correct
7 Incorrect 39 ms 1784 KB Output isn't correct
8 Incorrect 25 ms 1876 KB Output isn't correct
9 Incorrect 47 ms 1844 KB Output isn't correct
10 Incorrect 41 ms 1844 KB Output isn't correct
11 Incorrect 45 ms 1844 KB Output isn't correct
12 Incorrect 61 ms 1840 KB Output isn't correct
13 Incorrect 28 ms 1836 KB Output isn't correct
14 Incorrect 73 ms 1848 KB Output isn't correct
15 Incorrect 71 ms 1840 KB Output isn't correct
16 Incorrect 66 ms 1788 KB Output isn't correct
17 Incorrect 57 ms 1848 KB Output isn't correct
18 Incorrect 102 ms 1840 KB Output isn't correct
19 Incorrect 99 ms 1844 KB Output isn't correct
20 Incorrect 56 ms 1784 KB Output isn't correct