Cod sursa(job #2835363)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 18 ianuarie 2022 16:32:15
Problema Robotei Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX(1005);
vector<int> GT[NMAX * NMAX];
int n, m, x, y, modx, mody, offsetX, offsetY, dist[NMAX * NMAX], rez[NMAX * NMAX], G[NMAX * NMAX], cnt[NMAX][NMAX], l[NMAX], c[NMAX];
bool viz[NMAX * NMAX];
inline int getId(int i, int j)
{
    return i * m + j;
}

inline void DFST(int nod)
{
    for(auto it: GT[nod])
        if(dist[it] == -1)
        {
            dist[it] = dist[nod] + 1;
            DFST(it);
        }
}

int main()
{
    fin >> n >> m >> x >> y >> modx >> mody >> offsetX >> offsetY;

    for(int i = 0; i < n; ++i)
    {
        l[(i % modx * i % modx + offsetX) % modx]++;
        c[(i % mody * i % mody + offsetY) % mody]++;
    }
    for(int i = 0; i < modx; ++i)
        for(int j = 0; j < mody; ++j)
        {
            int newX = (i * i + offsetX) % modx, newY = (j * j + offsetY) % mody;
            G[getId(i, j)] = getId(newX, newY);
            GT[getId(newX, newY)].push_back(getId(i, j));
            dist[getId(i, j)] = -1;
            cnt[i][j] = l[i] * c[j];
        }

    int ok = -1;
    int nd = getId(x, y), nrP = 0;
    viz[nd] = 1;
    while(1)
    {
        nd = G[nd];
        ++nrP;
        if(viz[nd])
        {
            if(nd == getId(x, y))
                ok = 1;
            else ok = 0;
            break;
        }
        viz[nd] = 1;
    }

    nd = getId(x, y);
    dist[nd] = 0;
    DFST(nd);

    for(int i = 0; i < modx; ++i)
        for(int j = 0; j < mody; ++j){
            int nod = getId(i, j);
            if(dist[nod] != -1)
            {
                int times = 0;
                if(dist[nod] < m)
                {
                    ++times;
                    if(ok)
                        times += (m - 1 - dist[nod]) / nrP;
                }
                dist[nod] = times;
                rez[dist[nod]] += cnt[i][j];
            }
            else dist[nod] = 0;
        }


    rez[dist[G[nd]]]--;
    rez[dist[G[nd]] + 1]++;
    for(int i = 0; i <= m; ++i)
        if(rez[i])
            fout << i << ' ' << rez[i] << '\n';
    return 0;
}