Cod sursa(job #2115096)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 26 ianuarie 2018 12:09:40
Problema Robotei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
# include <fstream>
# define INF 1000000000
using namespace std;
ifstream fin("robotei.in");
ofstream fout("robotei.out");
struct ciclu{
    int lungimeCiclu,distantaPunct;
}d[1010][1010],val,aux;
int Marcat[1010][1010],n,m,x,y,modx,mody,offsetx,offsety,i,j;
int nexti(int i){
    return (i*i+offsetx)%modx;
}
int nextj(int j){
    return (j*j+offsety)%mody;
}
ciclu parcurge(int i,int j){
    int ic=i,jc=j,iv,jv,ok=0,nr=0,cnt=0,is,js;
    is=i;
    js=i;
    if(i>=modx||j>=mody){
        i=nexti(i);
        j=nextj(j);
    }
    while(Marcat[ic][jc]==0){
        Marcat[ic][jc]=1;
        if(ic==x&&jc==y)
            ok=1;
        ic=nexti(ic);
        jc=nextj(jc);
    }
    if(ok){
        ic=x;
        jc=y;
    }
    if(d[ic][jc].lungimeCiclu==0){
        nr=1;
        iv=nexti(ic);
        jv=nextj(jc);
        while(iv!=ic||jv!=jc){
            nr++;
            iv=nexti(iv);
            jv=nextj(jv);
        }
        while(d[ic][jc].lungimeCiclu==0){
            d[ic][jc].lungimeCiclu=nr;
            if(ok)
                d[ic][jc].distantaPunct=(nr-cnt)%nr;
            else
                d[ic][jc].distantaPunct=INF;
            cnt++;
            ic=nexti(ic);
            jc=nextj(jc);
        }
    }
    ic=i;
    jc=j;
    cnt=0;
    while(d[ic][jc].lungimeCiclu==0){
        cnt++;
        ic=nexti(ic);
        jc=nextj(jc);
    }
    ok=d[ic][jc].distantaPunct;
    ic=i;
    jc=j;
    while(d[ic][jc].lungimeCiclu==0){
        d[ic][jc].distantaPunct=ok+cnt;
        cnt--;
        d[ic][jc].lungimeCiclu=nr;
    }
    if(i!=is||j!=js){
        aux.distantaPunct=d[i][j].distantaPunct+1;
        aux.lungimeCiclu=d[i][j].lungimeCiclu;
        return aux;
    }
    else
        return d[i][j];
}
int main () {
    fin>>n>>m>>x>>y>>modx>>mody>>offsetx>>offsety;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++){
            if((i>=modx&&j>=mody)||(i<modx&&j<mody&&Marcat[i][j]==0)){
                if(i>=modx&&j>=mody)
                    val=parcurge(i,j);
                else
                    d[i][j]=parcurge(i,j);
            }
            if(i<modx&&j<mody)
                val=d[i][j];
            fout<<val.distantaPunct<<" "<<val.lungimeCiclu<<"\n";
            if(j==n-1)
                fout<<"\n\n";
        }
    return 0;
}