Submission #448264

# Submission time Handle Problem Language Result Execution time Memory
448264 2021-07-29T12:53:46 Z stefantaga Energetic turtle (IZhO11_turtle) C++14
50 / 100
2000 ms 2016 KB
#include <bits/stdc++.h>

using namespace std;
int frec[300005];
int fr[1005][1005],din[1005][1005][21];
long long k,t,z,n,m;
struct wow
{
    int x,y;
} v[105];
vector <int> prime;
bool c[300005];
long long 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;
}
map <pair <int,int> ,long long > mr;
long long nimicpr[105][105];
long long nr(int st,int dr)
{
    int x=v[st].x;
    int y=v[st].y;
    int x2=v[dr].x;
    int y2=v[dr].y;
    if (x>x2||y>y2)
    {
        swap(st,dr);
        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);
    }
    if (mr.find({st,dr})!=mr.end())
    {
            return mr[{st,dr}];
    }
    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)
            {
                inc=(inc-(1LL*nr(st,i)*combinari(x2-v[i].x,x2-v[i].x+y2-v[i].y))%z+z)%z;
            }
        }
    }
    mr[{st,dr}]=mr[{dr,st}]=inc;
    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;
}
bool compare(int a,int b)
{
    return v[a].x<v[b].x||(v[a].x==v[b].x&&v[a].y<v[b].y);
}
long long i,j;
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++;
    }
    v[0].x=1;
    v[0].y=1;
    v[k+1].x=n;
    v[k+1].y=m;
    lim=(1<<k);
    long long sum=nr(0,k+1);
    for (int i=1;i<lim;i++)
    {
        vector <int> sol;
        for (int j=0;j<k;j++)
        {
            if (i&(1<<j))
            {
                sol.push_back(j+1);
            }
        }
        int ok=1;
        sort (sol.begin(),sol.end(),compare);
        for (int j=1;j<sol.size();j++)
        {
            if (v[sol[j-1]].y>v[sol[j]].y)
            {
                ok=0;
                break;
            }
        }
        if (sol.size()>t)
        {
            ok=0;
        }
        if (ok==0)
        {
            continue;
        }
        long long p=nr(0,sol[0]);
        for (int j=1;j<sol.size();j++)
        {
            p=(p*nr(sol[j-1],sol[j]))%z;
        }
        int ult=(int)sol.size()-1;
        p=(p*nr(sol[ult],k+1))%z;
        sum=(sum+p)%z;
    }
    cout<<sum;
    return 0;
}

Compilation message

turtle.cpp: In function 'int main()':
turtle.cpp:196:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |         for (int j=1;j<sol.size();j++)
      |                      ~^~~~~~~~~~~
turtle.cpp:204:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  204 |         if (sol.size()>t)
      |             ~~~~~~~~~~^~
turtle.cpp:213:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  213 |         for (int j=1;j<sol.size();j++)
      |                      ~^~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 3 ms 1996 KB Output is correct
2 Correct 48 ms 1996 KB Output is correct
3 Correct 31 ms 2004 KB Output is correct
4 Correct 429 ms 1996 KB Output is correct
5 Correct 1619 ms 2012 KB Output is correct
6 Execution timed out 2090 ms 1996 KB Time limit exceeded
7 Correct 779 ms 2016 KB Output is correct
8 Correct 551 ms 2004 KB Output is correct
9 Correct 1438 ms 2008 KB Output is correct
10 Correct 660 ms 2016 KB Output is correct
11 Correct 1305 ms 1996 KB Output is correct
12 Execution timed out 2089 ms 1996 KB Time limit exceeded
13 Incorrect 235 ms 2016 KB Output isn't correct
14 Execution timed out 2076 ms 1996 KB Time limit exceeded
15 Execution timed out 2052 ms 1996 KB Time limit exceeded
16 Incorrect 1633 ms 2016 KB Output isn't correct
17 Incorrect 227 ms 2008 KB Output isn't correct
18 Execution timed out 2068 ms 1996 KB Time limit exceeded
19 Execution timed out 2069 ms 1996 KB Time limit exceeded
20 Incorrect 1493 ms 2016 KB Output isn't correct