Cod sursa(job #2596882)

Utilizator alex_benescuAlex Ben alex_benescu Data 10 aprilie 2020 16:34:27
Problema Robotei Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<cstdio>
#define MAXN 1005
#define MAXM 1000005
using namespace std;
int n, m, x, y, modx, mody, offsetx, offsety;
int X[MAXN], Y[MAXN], seen[MAXN][MAXN], answer[MAXM];
void DFS(int l,int c){
    int l0,c0;
    seen[l][c]=-1;
    l0=(l*l+offsetx)%modx;
    c0=(c*c+offsety)%mody;
    if(seen[l0][c0]==0)
        DFS(l0,c0);
    if(seen[l0][c0]!=-1)
        seen[l][c]=seen[l0][c0]+1;
}
int main(){
    freopen("robotei.in","r",stdin);
    freopen("robotei.out","w",stdout);
    int i,j,l,cycle;
    scanf("%d%d%d%d%d%d%d%d",&n, &m, &x, &y, &modx, &mody, &offsetx, &offsety);
    for(i=0;i<n;i++){
        X[(i*i+offsetx)%modx]++;
        Y[(i*i+offsety)%mody]++;
    }
    seen[x][y]=1;
    for(i=0;i<modx;i++)
        for(j=0;j<mody;j++)
            if(seen[i][j]==0)
                DFS(i,j);
    cycle=seen[(x*x+offsetx)%modx][(y*y+offsety)%mody];
    for(i=0;i<modx;i++)
        for(j=0;j<mody;j++){
            l=seen[i][j];
            if(l>0&&l<=m){
                if(cycle>0)
                    answer[1+(m-l)/cycle]+=X[i]*Y[j];
                else
                    answer[1]+=X[i]*Y[j];
            }
            else
                answer[0]+=X[i]*Y[j];
        }
    x=(x*x+offsetx)%modx;
    y=(y*y+offsety)%mody;
    if(cycle<=0){
        answer[0]--;
        answer[1]++;
    }
    else{
        answer[1+(m-seen[x][y])/cycle]--;
        answer[2+(m-seen[x][y])/cycle]++;
    }
    for(i=0;i<=m;i++)
        if(answer[i]!=0)
            printf("%d %d\n", i, answer[i]);
    return 0;
}