Cod sursa(job #2810542)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 29 noiembrie 2021 17:10:00
Problema Robotei Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int restl[1005];
int restc[1005];
int cnt[1005][1005];
int dist[1005][1005];
struct Celula
{
    int x,y;
};
vector<Celula> g[1005][1005];
int sol[667000];
int ciclu;
int offx,offy,modx,mody,x,y;
void dfs(int i, int j)
{
    ciclu++;
    dist[i][j]=1;
    int ii=(i*1LL*i+offx)%modx;
    int jj=(j*1LL*j+offy)%mody;
    if(ii==x && jj==y)
        return;
    if(dist[ii][jj]){
        ciclu=0;
        return;
    }
    dfs(ii, jj);
}
void dfs2(int xx, int yy, int pas)
{
    dist[xx][yy]=pas;
    for(int i=0; i<g[xx][yy].size(); i++)
        if(dist[g[xx][yy][i].x][g[xx][yy][i].y]==-1)
            dfs2(g[xx][yy][i].x, g[xx][yy][i].y, pas+1);
}
int main()
{   freopen("robotei.in", "r", stdin);
    freopen("robotei.out", "w", stdout);
    int n,m,i,j,ii,jj,xx,yy;
    scanf("%d%d%d%d%d%d%d%d", &n, &m, &x, &y, &modx, &mody, &offx, &offy);
    for(i=0; i<n; i++){
        restl[(i*1LL*i+offx)%modx]++;
        restc[(i*1LL*i+offy)%mody]++;
    }
    for(i=0; i<modx; i++)
        for(j=0; j<mody; j++)
            cnt[i][j]=restl[i]*restc[j];
    m--;
    for(i=0; i<modx; i++)
        for(j=0; j<mody; j++)
            if(cnt[i][j]){
                ii=(i*i+offx)%modx;
                jj=(j*j+offy)%mody;
                g[ii][jj].push_back({i, j});
            }
    dfs(x, y);
    memset(dist, -1, sizeof(dist));
    dfs2(x, y, 0);
    for(i=0; i<modx; i++)
        for(j=0; j<mody; j++){
            if(dist[i][j]>=0 && dist[i][j]<=m){
                if(ciclu)
                    dist[i][j]=1+(m-dist[i][j])/ciclu;
                else
                    dist[i][j]=1;
            }
            else
                dist[i][j]=0;
        }
    for(i=0; i<modx; i++)
        for(j=0; j<mody; j++)
            sol[dist[i][j]]+=cnt[i][j];
    xx=(x*1LL*x+offx)%modx;
    yy=(y*1LL*y+offy)%mody;
    sol[dist[xx][yy]]--;
    sol[dist[xx][yy]+1]++;
    for(i=0; i<=m; i++)
        if(sol[i])
            printf("%d %d\n", i, sol[i]);
    return 0;
}