Submission #448241

#	Time	Username	Problem	Language	Result	Execution time	Memory
448241		stefantaga	Energetic turtle (IZhO11_turtle)	C++14	5 / 100	2090 ms	1996 KiB

turtle

#include <bits/stdc++.h>

using namespace std;
int frec[300005];
int fr[1005][1005],din[1005][1005][21],k,t,z,n,m;
struct wow
{
    int x,y;
} v[105];
vector <int> prime;
bool c[300005];
long long j,i,lim;
long long ridput (long long a,long long b)
{
    if (b==0)
    {
        return 1;
    }
    long long rez=ridput(a,b/2);
    if (b%2==0)
    {
        return (rez*rez)%z;
    }
    return ((rez*rez)%z*a)%z;
}
void adauga(int n,int val)
{
    int j;
    for (j=0; j<(int)prime.size(); j++)
    {
        long long p=prime[j];
        while (p<=n)
        {
            frec[prime[j]]+=(n/p)*val;
            p=p*prime[j];
        }
    }
}
long long combinari(int k,int n)
{
    int j;
    for (j=0; j<(int)prime.size(); j++)
    {
        frec[prime[j]]=0;
    }
    adauga(n,1);
    adauga(k,-1);
    adauga(n-k,-1);
    long long p=1;
    for (j=0; j<(int)prime.size(); j++)
    {
        p=(p*ridput(prime[j],frec[prime[j]]))%z;
    }
    return p;
}
bool dif (int x,int y,int x2,int y2)
{
    if (x!=x2||y!=y2)
    {
        return 1;
    }
    return 0;
}
bool nimic(int x,int y,int x2,int y2)
{
    for (int i=1; i<=k; i++)
    {
        if (dif(v[i].x,v[i].y,x,y)==1&&dif(v[i].x,v[i].y,x2,y2)==1)
        {
            if (x<=v[i].x&&v[i].x<=x2&&y<=v[i].y&&v[i].y<=y2)
            {
                return 0;
            }
        }
    }
    return 1;
}
long long nr(int x,int y,int x2,int y2)
{
    if (x>x2||y>y2)
    {
        swap(x,x2);
        swap(y,y2);
    }
    long long inc=combinari(x2-x,x2-x+y2-y);
    if (nimic(x,y,x2,y2)==1)
    {
        return combinari(x2-x,x2-x+y2-y);
    }
    for (i=1;i<=k;i++)
    {
        if (dif(v[i].x,v[i].y,x,y)==1&&dif(v[i].x,v[i].y,x2,y2)==1)
        {
            if (x<=v[i].x&&v[i].x<=x2&&y<=v[i].y&&v[i].y<=y2)
            {
                if (nimic(x,y,v[i].x,v[i].y))
                {
                    inc=(inc-(nr(x,y,v[i].x,v[i].y)*combinari(x2-v[i].x,x2-v[i].x+y2-v[i].y))%z+z)%z;
                }
            }
        }
    }
    return inc;
}
long long brut()
{
    int i,j;
    for (i=1; i<=k; i++)
    {
        fr[v[i].x][v[i].y]=1;
    }
    din[1][1][0]=1;
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=m; j++)
        {
            if (i!=1||j!=1)
            {
                for (int r=fr[i][j]; r<=k; r++)
                {
                    din[i][j][r]=(din[i][j][r]+din[i-1][j][r-fr[i][j]]+din[i][j-1][r-fr[i][j]])%z;
                }
            }
        }
    }
    long long sum=0;
    for (int r=0; r<=t; r++)
    {
        sum=(sum+din[n][m][r])%z;
    }
    return sum;
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
#ifdef HOME
    ifstream cin("turtle.in");
    ofstream cout("turtle.out");
#endif // HOME
    cin>>n>>m>>k>>t>>z;
    n++;
    m++;
    lim=300000;
    c[0]=c[1]=1;
    for (i=2; i<=lim; i++)
    {
        if (c[i]==0)
        {
            prime.push_back(i);
            for (j=i*i; j<=lim; j+=i)
            {
                c[j]=1;
            }
        }
    }
    for (i=1; i<=k; i++)
    {
        cin>>v[i].x>>v[i].y;
        v[i].x++;
        v[i].y++;
    }
   // cout<<brut()<<'\n';
    lim=(1<<k);
    long long sum=nr(1,1,n,m);
    for (i=1;i<lim;i++)
    {
        vector <pair <int,int> > sol;
        for (j=0;j<k;j++)
        {
            if (i&(1<<j))
            {
                sol.push_back({v[i].x,v[i].y});
            }
        }
        int ok=1;
        sort (sol.begin(),sol.end());
        for (j=1;j<sol.size();j++)
        {
            if (sol[j-1].second>sol[j].second)
            {
                ok=0;
                break;
            }
        }
        if (sol.size()>t)
        {
            ok=0;
        }
        if (ok==0)
        {
            continue;
        }
        long long p=nr(1,1,sol[1].first,sol[1].second);
        for (j=1;j<sol.size();j++)
        {
            p=(p*nr(sol[j-1].first,sol[j-1].second,sol[j].first,sol[j].second))%z;
        }
        int ult=(int)sol.size()-1;
        p=(p*nr(sol[ult].first,sol[ult].second,n,m))%z;
        sum=(sum+p)%z;
    }
    cout<<sum;
    return 0;
}

Compilation message (stderr)

turtle.cpp: In function 'int main()':
turtle.cpp:178:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |         for (j=1;j<sol.size();j++)
      |                  ~^~~~~~~~~~~
turtle.cpp:186:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  186 |         if (sol.size()>t)
      |             ~~~~~~~~~~^~
turtle.cpp:195:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |         for (j=1;j<sol.size();j++)
      |                  ~^~~~~~~~~~~

• Subtask 1: 5 / 100