Cod sursa(job #904028)

Utilizator danalex97Dan H Alexandru danalex97 Data 3 martie 2013 16:40:36
Problema Robotei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

ifstream F("robotei.in");
ofstream G("robotei.out");

typedef struct{int x,y;} point;

point m_p(int x,int y)
{
    point out;
    out.x = x;
    out.y = y;
    return out;
}

const int Nmax = 1010;
const int Mmax = 666740;

int N,M,Mx,My,Ox,Oy,Cicle,X,Y;
vector<point> V[Nmax][Nmax];
int Go[Nmax][Nmax];
int A[Nmax][Nmax];
int Mark[Nmax][Nmax];
int Sol[Mmax];

int next_x(int x)
{
    return (x*x+Ox)%Mx;
}

int next_y(int y)
{
    return (y*y+Oy)%My;
}

int NX[Nmax];
int NY[Nmax];

int Find_cicle()
{
    int x=X,y=Y,Stop=Mx*My,i;
    x = NX[x];
    y = NY[y];
    for (i=1;i<Stop && !(x==X && y==Y);++i)
        x=NX[x],y=NY[y];
    if ( x != X || y != Y ) return M+1;
    return i;
}

#define IT(type) vector<type>::iterator

/*void BFS(int x,int y)
{
    queue<point> Q;

    Q.push(m_p(x,y));
    A[x][y] = 1;

    while ( Q.size() )
    {
        point nod = Q.front();
        Q.pop();

        for (IT(point) it=V[nod.x][nod.y].begin();it!=V[nod.x][nod.y].end();++it)
            if ( A[it->x][it->y] == 0 )
            {
                A[it->x][it->y] = A[nod.x][nod.y]+1;
                Q.push( *it );
            }
    }
}*/

int get_dist(int x,int y)
{
    if ( Mark[x][y] == 1 )
        return A[x][y];
    Mark[x][y] = 1;
    A[x][y] = get_dist( NX[x] , NY[y] );
    A[x][y] += ( A[x][y] != 0 );
    return A[x][y];
}

int main()
{
    F>>N>>M>>X>>Y;--N;
    F>>Mx>>My>>Ox>>Oy;

    for (int i=0;i<Mx;++i)
        for (int j=0;j<My;++j)
            Go[i][j]=( 1+(N-i)/Mx )*( 1+(N-j)/My );

    for (int i=0;i<Mx;++i) NX[i]=next_x(i);
    for (int i=0;i<My;++i) NY[i]=next_y(i);
    Cicle = Find_cicle();

    A[X][Y] = 1;
    Mark[X][Y] = 1;
    for (int i=0;i<Mx;++i)
        for (int j=0;j<My;++j)
            if ( Mark[i][j] == 0 )
                A[i][j] = get_dist(i,j);
    //BFS(X,Y);

    for (int i=0;i<Mx;++i)
        for (int j=0;j<My;++j)
            if ( A[i][j] > 0 )
            {
                --A[i][j];
                if ( A[i][j] > 0 && A[i][j] <= M )
                    A[i][j] = 1 + ( M - A[i][j] ) / Cicle;
            }
    A[X][Y] = 1 + M / Cicle;

    for (int i=0;i<Mx;++i)
        for (int j=0;j<My;++j)
            Sol[ A[i][j] ] += Go[i][j];
    Sol[ A[X][Y] ] -= Go[X][Y];
    Sol[ A[X][Y] ] += 1;
    Sol[ A[X][Y]-1 ] += Go[X][Y]-1;

    for (int i=0;i<=M;++i)
        if ( Sol[i] != 0 )
            G<<i<<' '<<Sol[i]<<'\n';
}