Cod sursa(job #1208547)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 16 iulie 2014 00:13:31
Problema Robotei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.06 kb
#include <fstream>
#include <bitset>

#define XMAX 1005
#define YMAX 1005
#define MMAX 666740
using namespace std;

int n,m,x,y,modx,mody,offsetx,offsety;

inline int x_next(int x)
{
    return (x*x+offsetx)%modx;
}

inline int y_next(int y)
{
    return (y*y+offsety)%mody;
}

long long int ans[MMAX];
int dist[XMAX][YMAX]; //Distanta de la (i,j) pana la (x,y) (in noduri)
bitset<YMAX> viz[XMAX];

int calc_dist(int x,int y)
{
    if(viz[x][y])
        return dist[x][y];
    viz[x][y]=1;

    int dist_next=calc_dist(x_next(x),y_next(y));
    if(!dist_next)
        return 0;

    dist[x][y]=dist_next+1;
    return dist[x][y];
}

long long int after[XMAX][YMAX]; //Cati roboti suplementari ajung la pozitia (i,j) dupa prima mutare

int main()
{
    ifstream cin("robotei.in");
    ofstream cout("robotei.out");

    cin>>n>>m>>x>>y>>modx>>mody>>offsetx>>offsety;

    if(x>=n || x<0 || y>=n || y<0){
        cout<<"0 "<<(1ll*n*n)<<'\n';

        cin.close();
        cout.close();
        return 0;
    }

    if(x>=modx || y>=mody){
        cout<<"0 "<<(1ll*n*n-1)<<'\n';
        cout<<"1 1\n";

        cin.close();
        cout.close();
        return 0;
    }

    //Acum avem o matrice de modx pe mod y
    viz[x][y]=1;
    dist[x][y]=1;

    for(int i=0;i<modx;i++)
        for(int j=0;j<mody;j++)
            calc_dist(i,j);

    //Acum graful arata asa:
    //dist[i][j] = 0 <=> Daca de la (i,j) nu se poate ajunge la (x,y)
    //Altfel, e distanta de la (i,j) la (x,y) (in noduri)
    for(int i=0;i<modx;i++)
        for(int j=0;j<mody;j++)
            after[x_next(i)][y_next(j)]+=((n-i-1ll)/modx+1ll)*((n-j-1ll)/mody+1ll)-1;

    int per=dist[x_next(x)][y_next(y)];

    if(!per){
        for(int i=0;i<modx;i++)
            for(int j=0;j<mody;j++)
                if(dist[i][j] && dist[i][j]<=m)
                    ans[1]+=(after[i][j]+1);
                else
                    ans[0]+=(after[i][j]+1);



        for(int i=0;i<=m;i++)
            if(ans[i])
                cout<<i<<' '<<ans[i]<<'\n';

        cin.close();
        cout.close();
        return 0;
    }

    //cout<<per<<'\n';

    m++; //Numarul de celule
    for(int i=0;i<modx;i++)
        for(int j=0;j<mody;j++)
            if(dist[i][j]){
                if(dist[i][j]<=m){
                    int cate=(m-dist[i][j])/per+1;
                    ans[cate]++;
                }
                else
                    ans[0]++;
            }
            else
                ans[0]++;

    m--;
    for(int i=0;i<modx;i++)
        for(int j=0;j<mody;j++)
            if(dist[i][j]){
                if(dist[i][j]<=m){
                    int cate=(m-dist[i][j])/per+1;
                    ans[cate]+=(after[i][j]);
                }
                else
                    ans[0]+=after[i][j];
            }
            else
                ans[0]+=after[i][j];

    for(int i=0;i<=m;i++)
        if(ans[i])
            cout<<i<<' '<<ans[i]<<'\n';

    cin.close();
    cout.close();
    return 0;
}