Cod sursa(job #1169057)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 10 aprilie 2014 13:05:34
Problema Robotei Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.38 kb
#include <fstream>
#include <cstring>

#define maxn 1000001

using namespace std;

ifstream fin ("robotei.in");
ofstream fout ("robotei.out");

int G[maxn],reach[maxn],dist[maxn],extra[maxn],cycle,n,m,M,X,Y,offx,offy,N;
long long ans[maxn];
int viz[maxn];

inline int node (const int &i,const int &j)
{
    return m*i + j;
}

void dfs (int x)
{
    viz[x] = cycle+1;

    if (!viz[G[x]])
        dfs (G[x]);

    if (viz[G[x]] == cycle + 1)
    {
        dist[x] = dist[G[x]] + 1;
        reach[x] = reach[G[x]];
    }
    else
    {
        dist[x] = 1;
        reach[x] = viz[G[x]];
    }

    if (cycle && reach[x] && M - (cycle-reach[x]) - dist[x] >= 0)
    {
        ans[1+ (M-(cycle-reach[x])-dist[x])/cycle]++;

        if (extra[x])
        {
            if (M - (cycle-reach[x]) - dist[x] - 1 >= 0)
            {
                ans[1+ (M-(cycle-reach[x])-dist[x]-1)/cycle] += extra[x];
            }
        }
    }
    else if (!cycle && reach[x] == 2)
    {
        if (M >= dist[x])
            ans[1] ++;

        if (extra[x])
        {
            if (M - 1 >= dist[x])
            {
                ans[1] += extra[x];
            }
        }
    }
}

int main()
{
    fin>>N>>M>>X>>Y>>n>>m>>offx>>offy;

    for (int i=0; i<n; ++i)
    {
        int rem = (i*i+offx)%n;

        for (int j=m; j<N; ++j)
        {
            extra[node(rem,(j*j+offy)%m)]++;
        }
    }

    for (int i=n; i<N; ++i)
    {
        int rem = (i*i+offx)%n;

        for (int j=0; j<m; ++j)
        {
            extra[node(rem,(j*j+offy)%m)]++;
        }
    }

    for (int i=n; i<N; ++i)
    {
        int rem = (i*i+offx)%n;

        for (int j=m; j<N; ++j)
        {
            extra[node(rem,(j*j+offy)%m)]++;
        }
    }

    if (X > n || Y > m)
    {
        fout<<0<<" "<<1;
        return 0;
    }

    for (int i=0; i<n; ++i)
    {
        for (int j=0; j<m; ++j)
        {
            G[node(i,j)] = node((i*i+offx)%n,(j*j+offy)%m);
        }
    }

    cycle = 0;

    for (int i=node(X,Y); ; i = G[i])
    {
        if (viz[i])
        {
            if (i != node(X,Y))
            {
                cycle = 0;
                memset (viz,0,sizeof(viz));
                viz[node(X,Y)] = 2;
            }

            break;
        }

        ++cycle;
        viz[i] = cycle;
    }

    if (cycle)
    {
        ans[1+M/cycle]++;
        viz[node(X,Y)] = cycle;

        if (extra[node(X,Y)])
        {
            if (M-1 > 0)
                ans[1+(M-1)/cycle] += extra[node(X,Y)];
        }

        for (int x = G[node(X,Y)],cnt=1; x != node(X,Y); x = G[x],++cnt)
        {
            viz[x] = cnt;

            if (M - (cycle-viz[x]) >= 0)
            {
                ans[1 + (M-(cycle-viz[x]))/cycle]++;
            }

            if (extra[x])
            {
                if (M - (cycle-viz[x]) - 1 >= 0)
                {
                    ans[1 + (M-(cycle-viz[x])-1)/cycle] += extra[x];
                }
            }
        }
    }
    else ans[1] ++;

    for (int i=0; i<=n*m-1; ++i)
    {
        if (!viz[i])
            dfs (i);
    }

    long long s = 0;

    for (int i=1; i <=M; ++i)
        s += ans[i];
    ans[0] = 1LL*N*N-s;

    for (int i=0; i<=M; ++i)
    {
        if (ans[i])
            fout<<i<<" "<<ans[i]<<"\n";
    }
}