Cod sursa(job #2030680)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 1 octombrie 2017 23:05:15
Problema Robotei Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.29 kb
#include <bits/stdc++.h>

#define INF 1000000000
#define MAXN 1000
struct Point{
    int x, y;
};
struct gw4oigwb{
    Point next;
    int app;
    int gud = 0;
    int dist;
}d[MAXN][MAXN];

int waiting = -1, good, bad, idle = 0;

void goLukEtIt(int x, int y){
    d[x][y].gud = -1;
    int newx = d[x][y].next.x, newy = d[x][y].next.y;

    if(d[newx][newy].gud == waiting){
        d[x][y].gud = bad;
        return ;
    }
    if(d[newx][newy].gud == idle)
        goLukEtIt(newx, newy);

    if(d[newx][newy].gud == bad)
        d[x][y].gud = bad;
    else if(d[newx][newy].gud == good){
        d[x][y].gud = good;
        d[x][y].dist = d[newx][newy].dist + 1;
    }
}

int vx[1 + MAXN], vy[1 + MAXN];
int vx2[1 + MAXN], vy2[1 + MAXN];

long long rez[1000010];

int main(){
    FILE*fi,*fo;
    fi = fopen("robotei.in","r");
    fo = fopen("robotei.out","w");

    int n, m, x, y, modx, mody, offsetx, offsety;
    fscanf(fi,"%d%d%d%d%d%d%d%d", &n, &m, &x, &y, &modx, &mody, &offsetx, &offsety);

    for(int i = 0; i < modx; i++)
        for(int j = 0; j < mody; j++){
            d[i][j].next.x = (i * i + offsetx) % modx;
            d[i][j].next.y = (j * j + offsety) % mody;
        }

    int indx, indy;
    indx = x;
    indy = y;
    int dist = 0;
    while(d[indx][indy].app == 0){
        d[indx][indy].dist = dist ++;
        d[indx][indy].app = 1;
        d[indx][indy].gud = 1;
        int prevx = indx, prevy = indy;
        indx = d[prevx][prevy].next.x;
        indy = d[prevx][prevy].next.y;
    }

    int cyc;
    if(indx == x && indy == y){
        good = 1;
        bad = 2;
        cyc = dist;
    }
    else{
        d[x][y].gud = 2;
        good = 2;
        bad = 1;
        d[x][y].dist = 0;
        cyc = INF;
    }

    for(int i = 0; i < modx; i++)
        for(int j = 0; j < mody; j++)
            if(d[i][j].gud == idle) goLukEtIt(i, j);
    /*for(int i = 0; i < modx; i++){
        for(int j = 0; j < mody; j++)
            printf("%d ", d[i][j].dist);
        printf("\n");
    }*/

    for(int i = modx; i < n; i++){
        int nx = (i * i + offsetx) % modx;
        vx[nx] ++;
    }
    for(int i = 0; i < modx; i++){
        int nx = (i * i + offsetx) % modx;
        vx2[nx] ++;
    }
    for(int j = mody; j < n; j++){
        int ny = (j * j + offsety) % mody;
        vy[ny] ++;
    }
    for(int j = 0; j < mody; j++){
        int ny = (j * j + offsety) % mody;
        vy2[ny] ++;
    }

    for(int i = 0; i < modx; i++)
        for(int j = 0; j < mody; j++){
            long long nr = 1LL* vx[i] * (vy[j] + vy2[j]) + 1LL * vx2[i] * vy[j];
            if(d[i][j].gud == bad || (d[i][j].gud == good && d[i][j].dist + 1 > m)) rez[0] += nr;
            else rez[1 + (m - d[i][j].dist - 1)/cyc] += nr;

            if(d[i][j].gud == bad || (d[i][j].gud == good && d[i][j].dist > m)) rez[0] ++;
            else rez[1 + (m - d[i][j].dist)/cyc] ++;
        }
    for(int i = 0; i <= 1000000; i++)
        if(rez[i] > 0)
            fprintf(fo,"%d %d\n", i, rez[i]);

    /*for(int i = 0; i < n; i++)
        printf("%d ", (i * i + offsetx) % modx);
    printf("\n");
    for(int j = 0; j < n; j++)
        printf("%d ", (j * j + offsety) % mody);*/
    fclose(fi);
    fclose(fo);
    return 0;
}