Cod sursa(job #2109029)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 19 ianuarie 2018 01:04:13
Problema Robotei Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 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];
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;
    } }
    
    dfs(make_pair(x, y), 0);
    
    for (int i = 0; i < modx; ++i) {
    for (int j = 0; j < mody; ++j) {
        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;
}