Cod sursa(job #2630931)

Utilizator david.teacaDavid Stefan Teaca david.teaca Data 28 iunie 2020 10:38:05
Problema Robotei Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.18 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;
}