Cod sursa(job #2030693)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 1 octombrie 2017 23:26:21
Problema Robotei Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.47 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);
    if(x >= modx || y >= mody){
        fprintf(fo,"0 %d\n1 1", n * n - 1);
        return 0;
    }
    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 = 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]);

    fclose(fi);
    fclose(fo);
    return 0;
}

/*#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("a.in", "r");
    fout=fopen("a.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)){
        fprintf(fout, "0 %d\n", n*n);
        return 0;
    }

    if((xs>=a)||(ys>=b)){
        fprintf(fout, "0 %d\n1 1\n", n*n-1);
        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, ajut=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 ajut++;
                }
                if((d[i][j]+1<=m)&&(v[i]*g[j]-qw[i]*er[j])){
                    if(t) r[k++]=mp(1+(m-d[i][j]-1)/c, v[i]*g[j]-qw[i]*er[j]);
                    else ajut+=v[i]*g[j]-qw[i]*er[j];
                }
            }
        }
    }

    if(ajut)
        r[k++]=mp(1, ajut);

    int sum=n*n;
    for(int i=0; i<k; i++)
        sum-=r[i].y;

    if(sum)
        r[k++]=mp(0, sum);

    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;
}*/