Cod sursa(job #1185739)

Utilizator misinoonisim necula misino Data 16 mai 2014 17:50:51
Problema Robotei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include<fstream>

#define N 1100
#define M 700000

using namespace std;

ifstream f("robotei.in");
ofstream g("robotei.out");

int n,m,x,y,modx,mody,i,osx,osy,j,a,lg,b,sol[M],urmx[N],urmy[N],viz[N][N],d[N][N],cate[N][N];

inline int nextx(int x){
    return (1LL * x * x + osx) % modx;
}

inline int nexty(int y){
    return (1LL * y * y + osy) % mody;
}

inline int distanta(int x, int y){
    if(viz[x][y])
        return d[x][y];

    viz[x][y] = 1;
    d[x][y] = distanta(urmx[x] , urmy[y]);

    if(d[x][y])
        ++ d[x][y];

    return d[x][y];
}

int main()
{
    f >> n >> m >> x >> y >> modx >> mody >> osx >> osy;

    -- n ;

    ///Precalculez urmatoarea pozitie

    for(i = 0 ; i < modx ; ++ i)
        urmx[i] = nextx(i);

    for(j = 0 ; j < mody ; ++ j)
        urmy[j] = nexty(j);


    ///Fac ciclu

    a = nextx(x);
    b = nexty(y);

    lg = 1;

    while(x != a || y != b)
    {
        a = urmx[a];
        b = urmy[b];

        ++ lg;

        if(lg == modx * mody)
            break;
    }

    if(lg == modx * mody)
        lg = m + 1;


    ///Distanta de la fiecare celula la (x , y)
    d[x][y] = 1;
    viz[x][y] = 1;

    for(i = 0 ; i < modx ; ++ i )
        for(j = 0 ; j < mody ; ++ j)
        if(!viz[i][j])
        d[i][j] = distanta(i , j);

    ///cate[i][j] = Cate pozitii sunt echivalente cu i,j

    for(i = 0 ; i < modx ; ++ i)
        for(j = 0 ; j < mody ; ++ j)
    {
        cate[i][j] = (1 + (n - i) / modx) * (1 + (n - j) / mody);
    }

    ///Calculare solutii

    for(i = 0 ; i < modx ; ++ i)
        for(j = 0 ; j < mody ; ++ j)
            if(d[i][j])
        {
            -- d[i][j];

            if(d[i][j] && d[i][j] <= m)
                d[i][j] = 1 + (m - d[i][j]) / lg;
        }
    d[x][y] = 1 + m / lg;

    for(i = 0 ; i < modx ; ++ i)
        for(j = 0 ; j < mody ; ++ j)
        sol[d[i][j]] += cate[i][j];

    sol[d[x][y]] -= cate[x][y];
    ++ sol[d[x][y]] ;
    sol[d[x][y] - 1] += cate[x][y] - 1;

    for(i = 0 ; i <= m ; ++ i)
        if(sol[i])
        g << i << ' ' << sol[i] << '\n';

    return 0;
}