Cod sursa(job #2603606)

Utilizator alexradu04Radu Alexandru alexradu04 Data 20 aprilie 2020 14:24:08
Problema Robotei Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb

#include <bits/stdc++.h>
using namespace std;

ifstream in("robotei.in");
ofstream out("robotei.out");


const int NMAX = 44340;
const int MMAX = 666733;
const int LMAX = 1001;

bitset<LMAX> oki[LMAX];
vector<pair<int, int>> edg[LMAX][LMAX];

int cntx[LMAX], cnty[LMAX], stp1[LMAX][LMAX], opt[LMAX];
int nxtx[NMAX], nxty[NMAX], ans[MMAX], dst[LMAX][LMAX];

void dfs(pair<int, int> x, int l)
{
    dst[x.first][x.second] = l;
    for (pair<int, int> y : edg[x.first][x.second])
        if (dst[y.first][y.second] == -1) dfs(y, l + 1);
}

int main(void)
{
    int n, m, x, y, modx, mody, ofsx, ofsy;
    in >> n >> m >> x >> y >> modx >> mody >> ofsx >> ofsy;

    for (int i = 0; i < n; ++i) {
        nxtx[i] = (i * i + ofsx) % modx; ++cntx[nxtx[i]];
        nxty[i] = (i * i + ofsy) % mody; ++cnty[nxty[i]];
    }

    int len = -1;
    for (int _x = x, _y = y, i = 1; i <= modx * mody; ++i) {
        _x = nxtx[_x]; _y = nxty[_y];

        if (_x == x and _y == y) {
            len = i;
            break;
        }
    }

    for (int i = 0; i < modx; ++i) {
        for (int j = 0; j < mody; ++j) {
            edg[nxtx[i]][nxty[j]].push_back(make_pair(i, j));

            stp1[i][j] = cntx[i] * cnty[j];
            dst[i][j] = -1; opt[i] += stp1[i][j] > 0;
        } }

    dfs(make_pair(x, y), 0);
    for (int i = 0; i < modx; ++i) if (opt[i]) {
            for (int j = 0; j < mody; ++j) {
                if (!stp1[i][j]) continue;
                bool ok = (i == nxtx[x]) and (j == nxty[y]);

                if (dst[i][j] == -1) {
                    ans[0] += stp1[i][j] - ok;
                    ans[ok] += ok;
                } else
                if (len == -1) {
                    ans[dst[i][j] < m] += stp1[i][j] - ok;
                    ans[(dst[i][j] < m) + ok] += ok;
                } else
                if (dst[i][j] < m) {
                    ans[(m - dst[i][j] - 1) / len + 1] += stp1[i][j] - ok;
                    ans[(m - dst[i][j] - 1) / len + 1 + ok] += ok;
                }
            } }

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

    return 0;
}