Cod sursa(job #1965273)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 14 aprilie 2017 11:17:41
Problema Robotei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.17 kb
#include <cstdio>
#include <utility>
#include <algorithm>

#define mp std::make_pair
#define x first
#define y second

#define MAXN 1000

bool viz[MAXN+1][MAXN+1];
int d[MAXN+1][MAXN+1], g[MAXN+1], v[MAXN+1], qw[MAXN+1], er[MAXN+1];
struct myc{
    short int x, y;
}u[MAXN+1][MAXN+1];

std::pair <int, int> r[MAXN*MAXN];

int n, m, xs, ys, a, b, vx, vy, oldx, oldy;

inline void next(){
    oldx=xs;
    oldy=ys;
    xs=(1LL*oldx*oldx+vx)%a;
    ys=(1LL*oldy*oldy+vy)%b;
}

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

    fscanf(fin, "%d%d%d%d%d%d%d%d", &n, &m, &xs, &ys, &a, &b, &vx, &vy);

    if((xs>=n)||(ys>=n)) return 0;

    if((xs>=a)||(ys>=b)){
        fprintf(fout, "1 1\n");
        return 0;
    }

    viz[xs][ys]=1;
    d[xs][ys]=0;

    next();

    int c=1;
    while(viz[xs][ys]==0){
        viz[xs][ys]=1;
        u[xs][ys].x=oldx;
        u[xs][ys].y=oldy;
        d[xs][ys]=-1;
        c++;
        next();
    }

    bool t;
    if(d[xs][ys]==0) t=1;
    else t=0;

    if(t){
        xs=oldx;
        ys=oldy;

        int l=1;
        while(d[xs][ys]==-1){
            d[xs][ys]=l;
            l++;

            int aux=xs;
            xs=u[xs][ys].x;
            ys=u[aux][ys].y;
        }
    }

    for(int i=0; i<a; i++){
        for(int j=0; j<b; j++){
            if(viz[i][j]==0){
                xs=i;
                ys=j;
                while(viz[xs][ys]==0){
                    viz[xs][ys]=1;
                    d[xs][ys]=-1;
                    u[xs][ys].x=oldx;
                    u[xs][ys].y=oldy;
                    next();
                }

                int l=d[xs][ys];

                if(l!=-1){
                    xs=oldx;
                    ys=oldy;

                    while((xs!=i)||(ys!=j)){
                        l++;
                        d[xs][ys]=l;

                        int aux=xs;
                        xs=u[xs][ys].x;
                        ys=u[aux][ys].y;
                    }

                    l++;
                    d[i][j]=l;
                }
            }
        }
    }

    for(int i=0; i<n; i++){
        xs=i;
        next();

        v[xs]++;
        if(i<a) qw[xs]++;
    }

    for(int i=0; i<n; i++){
        ys=i;
        next();

        g[ys]++;
        if(i<b) er[ys]++;
    }

    int k=0;
    for(int i=0; i<a; i++){
        for(int j=0; j<b; j++){
            if(d[i][j]!=-1){
                if(d[i][j]<=m){
                    if(t) r[k++]=mp(1+(m-d[i][j])/c, 1);
                    else r[k++]=mp(1, 1);
                }
                if(d[i][j]+1<=m){
                    if(t) r[k++]=mp(1+(m-d[i][j]-1)/c, v[i]*g[j]-qw[i]*er[j]);
                    else r[k++]=mp(1, v[i]*g[j]-qw[i]*er[j]);
                }
            }
        }
    }

    std::sort(r, r+k);

    int q=k;
    k=1;
    for(int i=1; i<q; i++)
        if(r[i].x==r[k-1].x) r[k-1].y+=r[i].y;
        else r[k++]=r[i];

    for(int i=0; i<k; i++)
        fprintf(fout, "%d %d\n", r[i].x, r[i].y);

    fclose(fin);
    fclose(fout);
    return 0;
}