Cod sursa(job #3147030)

Utilizator catalinmarincatalinmarin catalinmarin Data 23 august 2023 19:16:15
Problema Robotei Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.88 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("robotei.in");
ofstream cout("robotei.out");
int main(){
    int frecv_x[1001] = {0};
    int frecv_y[1001] = {0};
    int robotei[1001][1001];
    int dist[1001][1001];
    int frecvente_robotei_xy[44440];
    int n, m, x, y, mod_x, mod_y, offx, offy;
    cin >> n >> m >> x >> y >> mod_x >> mod_y >> offx >> offy;
    for (int i = 0; i < mod_x; i++){
        for (int j = 0; j < mod_y; j++){
            dist[i][j] = -1;
        }
    }
    for (int i = 0; i < n; i++){
        int new_x = (i * i + offx) % mod_x;
        int new_y = (i * i + offy) % mod_y;
        frecv_x[new_x]++;
        frecv_y[new_y]++;
    }
    for (int i = 0; i < mod_x; i++){
        for (int j = 0; j < mod_y; j++){
            robotei[i][j] = frecv_x[i] * frecv_y[j];
        }
    }
    int xy_cycle_time = 1;
    int temp_x = (x * x + offx) % mod_x, temp_y = (y * y + offy) % mod_y;
    while (temp_x != x || temp_y != y){
        xy_cycle_time++;
        temp_x = (temp_x * temp_x + offx) % mod_x;
        temp_y = (temp_y * temp_y + offy) % mod_y;
    }
    int temp_xy_cycle_time = xy_cycle_time;
    temp_x = (x * x + offx) % mod_x;
    temp_y = (y * y + offy) % mod_y;
    while (temp_x != x || temp_y != y){
        temp_xy_cycle_time--;
        dist[temp_x][temp_y] = temp_xy_cycle_time;
        temp_x = (temp_x * temp_x + offx) % mod_x;
        temp_y = (temp_y * temp_y + offy) % mod_y;
    }
    dist[x][y] = 0;
    for (int i = 0; i < mod_x; i++){
        for (int j = 0; j < mod_y; j++){
            if (dist[i][j] != -1){
                continue;
            } else {
                vector<pair<int, int>> path;
                pair<int, int> point;
                point.first = i;
                point.second = j;
                path.push_back(point);
                while (dist[point.first][point.second] == -1){
                    point.first = (point.first * point.first + offx) % mod_x;
                    point.second = (point.second * point.second + offy) % mod_y;
                    path.push_back(point);
                }
                for (int k = path.size() - 2; k >= 0; k--) {
                    dist[path[k].first][path[k].second] = dist[path[k + 1].first][path[k + 1].second] + 1;
                }
            }
        }
    }
    for (int i = 0; i < mod_x; i++){
        for (int j = 0; j < mod_y; j++){
            if (dist[i][j] != 0) {
                int nr_xy_cycles = ((m - dist[i][j] - 1) / xy_cycle_time + 1);
                frecvente_robotei_xy[nr_xy_cycles] += robotei[i][j];
            } else {
                int nr_xy_cycles = m / xy_cycle_time + 1;
                frecvente_robotei_xy[nr_xy_cycles] += 1;
                frecvente_robotei_xy[nr_xy_cycles - 1] += robotei[i][j] - 1;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << i << " " << frecvente_robotei_xy[i] << '\n';
    }
    return 0;
}