Cod sursa(job #2030718)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 2 octombrie 2017 00:21:15
Problema Robotei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.64 kb
#include <bits/stdc++.h>

#define INF 1000000000
#define MAXN 1005
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 ++;
        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;
        indx = d[x][y].next.x;
        indy = d[x][y].next.y;
        d[x][y].dist = 0;
        int l = cyc - 1;
        while(indx != x || indy != y){
            d[indx][indy].dist = l;
            l = (l + cyc - 1) % cyc;
            int prevx = indx, prevy = indy;
            indx = d[prevx][prevy].next.x;
            indy = d[prevx][prevy].next.y;
        }
    }
    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]);
    /*printf("%d ", cyc);
    for(int i = 0; i < modx; i++){
        for(int j = 0; j < mody; j++)
            printf("%d %02d    ", d[i][j].gud, d[i][j].dist);
        printf("\n");
    }*/

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