Cod sursa(job #842120)

Utilizator stoicatheoFlirk Navok stoicatheo Data 26 decembrie 2012 10:33:09
Problema Robotei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int XY_MAX = 1000;
const int M_MAX = 666733;

int n, m, modX, modY, offX, offY;
int stepInX[XY_MAX], stepInY[XY_MAX];
int stepOutX[XY_MAX], stepOutY[XY_MAX];
int qx, qy;
int cycle;
int dist[XY_MAX][XY_MAX];
int ans[M_MAX];

inline int nextX ( int x ) { return (int)(((long long)x*x + offX) % modX); }
inline int nextY ( int y ) { return (int)(((long long)y*y + offY) % modY); }

void pack() {
    for (int x = 0; x < modX; ++x)
        ++stepInX[nextX(x)];
    for (int y = 0; y < modY; ++y)
        ++stepInY[nextY(y)];
    for (int x = modX; x < n; ++x)
        ++stepOutX[nextX(x)];
    for (int y = modY; y < n; ++y)
        ++stepOutY[nextY(y)];


}

inline int outOfRange ( int x, int y ) { return stepInX[x] * stepOutY[y] + stepOutX[x] * stepInY[y] + stepOutX[x] * stepOutY[y]; }

int getPointDistance ( int x, int y ) {
    if (x == qx && y == qy)
        return dist[x][y] = 0;

    dist[x][y] = m+1;
    int nx = nextX(x);
    int ny = nextY(y);
    if (dist[nx][ny] != 0 || (x == qx && y == qy))
        dist[x][y] = dist[nx][ny] + 1; else
        dist[x][y] = getPointDistance(nx, ny) + 1;

    return dist[x][y];
}

void getAllDistances() {
    for (int x = 0; x < modX; ++x)
        for (int y = 0; y < modY; ++y)
            if (dist[x][y] == 0 && (x != qx || y != qy))
                getPointDistance(x, y);
    cycle = dist[nextX(qx)][nextY(qy)] + 1;


}

void getPasses() {
    if (qx >= modX || qy >= modY) {
        ans[0] = n*n-1;
        ans[1] = 1;
        return;
    }

    for (int x = 0; x < modX; ++x) {
        for (int y = 0; y < modY; ++y) {
            int passes = 0, plus = 0;
            if (dist[x][y] <= m)
                passes = 1 + (m - dist[x][y]) / cycle;
            if (dist[x][y] < m)
                plus = 1 + (m - dist[x][y] - 1) / cycle;

            ++ans[passes];
            ans[plus] += outOfRange(x,y);
        }
    }
}

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

    fin >> n >> m >> qx >> qy >> modX >> modY >> offX >> offY;

    pack();
    getAllDistances();
    getPasses();

    for (int i = 0; i <= m; ++i)
        if (ans[i] > 0)
            fout << i << ' ' << ans[i] << '\n';

    return 0;
}