Cod sursa(job #2120118)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 1 februarie 2018 22:05:51
Problema Robotei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <cstdio>

using namespace std;

const int MAX_M = 1000;

int fx[MAX_M + 5], fy[MAX_M + 5];
int d[MAX_M + 5][MAX_M + 5], ajung[MAX_M + 5][MAX_M + 5], viz[MAX_M + 5][MAX_M + 5];
int ans[666735];
int mx, my, ox, oy;

int nxt(int c, int o, int m) {
  return (c * c + o) % m;
}

void dfs(int x, int y) {
  viz[x][y] = 1;
  int x1 = nxt(x, ox, mx), y1 = nxt(y, oy, my);
  if (!viz[x1][y1])
    dfs(x1, y1);
  ajung[x][y] = ajung[x1][y1];
  d[x][y] = 1 + d[x1][y1];
}

int main() {
  freopen("robotei.in", "r", stdin);
  freopen("robotei.out", "w", stdout);

  int n, m, x, y;
  scanf("%d%d%d%d%d%d%d%d", &n, &m, &x, &y, &mx, &my, &ox, &oy);
  for (int i = mx; i <= n; ++i)
    fx[nxt(i, ox, mx)]++;
  for (int i = my; i <= m; ++i)
    fy[nxt(i, oy, my)]++;
  viz[x][y] = ajung[x][y] = 1;
  for (int i = 0; i < mx; ++i)
    for (int j = 0; j < my; ++j)
      if (!viz[i][j])
        dfs(i, j);
  int x1 = nxt(x, ox, mx), y1 = nxt(y, oy, my), c = -1;
  if (ajung[x1][y1])
    c = 1 + d[x1][y1];
  ans[1] = 1;
  for (int i = 0; i < mx; ++i)
    for (int j = 0; j < my; ++j)
      if (ajung[i][j]) {
        int nr = fx[i] * fy[j];
        if (c == -1) {
          if (d[i][j] + 1 <= m)
            ans[1] += nr;
          else
            ans[0] += nr;
          if (d[i][j] <= m)
            ans[1]++;
          else
            ans[0]++;
        } else {
          if (d[i][j] + 1 <= m)
            ans[1 + (m - d[i][j] - 1) / c] += nr;
          else
            ans[0] += nr;
          if (d[i][j] <= m)
            ans[1 + (m - d[i][j]) / c] += nr;
          else
            ans[0]++;
        }
      }

  for (int i = 0; i <= m; ++i)
    if (ans[i])
      printf("%d %d\n", i, ans[i]);
  return 0;
}