Cod sursa(job #1169045)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 10 aprilie 2014 12:31:33
Problema Robotei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.12 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],ans[maxn],extra[maxn],cycle,n,m,M,modx,mody,X,Y,offx,offy;
int viz[maxn];

inline int node (int i, 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>>modx>>mody>>offx>>offy;

    m = n;

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

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

    n = min (n,modx);
    m = min (m,mody);

    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)%modx,(j*j+offy)%mody);
        }
    }

    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);
    }

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