Cod sursa(job #815114)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 16 noiembrie 2012 17:05:01
Problema Robotei Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.98 kb
#include<stdio.h>
#include<bitset>

#define maxn 45000
#define maxm 700000
#define maxmod 1005

using namespace std;

FILE*f=fopen("robotei.in","r");
FILE*g=fopen("robotei.out","w");

const int inf = (1<<29);
int n,m,xs,ys,modx,mody,offsetx,offsety;
int nextx[maxn],nexty[maxn],catix[maxmod],catiy[maxmod],dist[maxmod][maxmod],C[2][maxmod*maxmod];
int acum[maxmod][maxmod],sol[maxm];
bitset<maxmod>viz[maxmod];

inline void solve () {
	
	if ( xs >= n || ys >= n ){
		fprintf(g,"%d %d\n",0,1);
		return ;
	}
	
	for ( int i = 0 ; i < modx ; ++i ){
		for ( int j = 0 ; j < mody ; ++j ){
			
			if ( viz[i][j] || (i == xs && j == ys) )	continue ;
			
			int left = 1,right = 0; viz[i][j] = 1; acum[i][j] = 1;
			++right; C[0][right] = i,C[1][right] = j;
			while ( left <= right ){
				int xv = nextx[C[0][left]],yv = nexty[C[1][left]];
				
				if ( !viz[xv][yv] ){
					++right;
					C[0][right] = xv,C[1][right] = yv;
					viz[xv][yv] = 1; acum[xv][yv] = right;
				}
				else{
					if ( acum[xv][yv] ){
						//ciclu
						if ( !acum[xs][ys] ){
							
							for ( int i = 1 ; i <= right ; ++i ){
								dist[C[0][i]][C[1][i]] = inf;
							}
						}
						else{
							int p = acum[xs][ys];
							
							for ( int i = 1 ; i < p ; ++i ){
								dist[C[0][i]][C[1][i]] = p-i;
							}
							
							if ( acum[xv][yv] > p ){
								for ( int i = p+1 ; i <= right ; ++i ){
									dist[C[0][1]][C[1][i]] = inf;
								}
							}
							else{
								for ( int i = p+1 ; i <= right ; ++i ){
									dist[C[0][i]][C[1][i]] = right-p+1 + p-acum[xv][yv];
								}
							}
						}
					}
					else{
						//deja calculat
						int distanta = 0;
						for ( int index = right ; index >= 1 ; --index ){
							++distanta;
							dist[C[0][index]][C[1][index]] = dist[xv][yv] + distanta;
							if ( dist[C[0][index]][C[1][index]] >= inf )	dist[C[0][index]][C[1][index]] = inf;
						}
					}
					break ;
				}
				
				++left;
			}
			
			for ( int index = 1 ; index <= right ; ++index ){
				acum[C[0][index]][C[1][index]] = 0;
				C[0][index] = C[1][index] = 0;
			}
		}
	}
	
	int cycle = 0,X = xs,Y = ys;
	do{
		++cycle;
		X = nextx[X]; Y = nexty[Y];
	}while( (X != xs || Y != ys) && cycle <= modx*mody+2);
	
	if ( cycle == modx*mody+3 ){
		cycle = m+1;
	}
	
	--m;
	for ( int i = 0 ; i < modx ; ++i ){
		for ( int j = 0 ; j < mody ; ++j ){
			
			int turns = 0;
			if ( dist[i][j] <= m ){
				turns = 1 + (m-dist[i][j])/cycle;
			}
			sol[turns] += catix[i]*catiy[j];
		}
	}
	++m;
	--sol[m/cycle]; ++sol[1+m/cycle];
	
	for ( int i = 0 ; i <= m ; ++i ){
		if ( sol[i] ){
			fprintf(g,"%d %d\n",i,sol[i]);
		}
	}
}

int main () {
	
	fscanf(f,"%d %d %d %d %d %d %d %d",&n,&m,&xs,&ys,&modx,&mody,&offsetx,&offsety);
	
	for ( int i = 0 ; i < n ; ++i ){
		nextx[i] = (i*i+offsetx)%modx;
		nexty[i] = (i*i+offsety)%mody;
		++catix[nextx[i]]; ++catiy[nexty[i]];
	}
	
	solve();
	
	fclose(f);
	fclose(g);
	
	return 0;
}