Cod sursa(job #3247179)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 6 octombrie 2024 10:28:38
Problema Robotei Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
// Ilie "The-Winner" Dumitru
#include<cstdio>
const int NMAX=1024, MMAX=700000;

int N, M, modX, modY, offX, offY, tarX, tarY;
bool vis[NMAX][NMAX];
long long time[NMAX][NMAX], cnt[NMAX][NMAX];
long long period;
long long answers[MMAX];

int dfs(int x, int y)
{
	if(x==tarX && y==tarY)
		return 0;

	if(vis[x][y])
		return time[x][y];

	vis[x][y]=1;
	time[x][y]=-1;

	int aux=dfs((x*x+offX)%modX, (y*y+offY)%modY);
	if(aux!=-1)
		time[x][y]=aux+1;
	return time[x][y];
}

void update(int x, int y)
{
	if(time[x][y]==-1 || time[x][y]>M)
	{
		answers[0]+=cnt[x][y];
		return;
	}

	if(x==tarX && y==tarY)
	{
		if(period==-1)
		{
			++answers[1];
			return;
		}

		answers[M/period+1]+=1;

		int c=cnt[x][y]-1;
		x=(x*x+offX)%modX;
		y=(y*y+offY)%modY;

		int passes=0, left=M-1;

		if(time[x][y]>left)
		{
			answers[0]+=c;
			return;
		}

		left-=time[x][y];
		++passes;
		passes+=left/period;

		answers[passes]+=c;
	}
	else
	{
		if(period==-1)
		{
			answers[1]+=cnt[x][y];
			return;
		}

		int passes=0, left=M;

		left-=time[x][y];
		++passes;
		passes+=left/period;

		answers[passes]+=cnt[x][y];
	}
}

int main()
{
	FILE* f=fopen("robotei.in", "r"), *g=fopen("robotei.out", "w");
	int i, j;

	fscanf(f, "%d%d%d%d%d%d%d%d", &N, &M, &tarX, &tarY, &modX, &modY, &offX, &offY);

	for(i=0;i<modX;++i)
		for(j=0;j<modY;++j)
		{
			if(!vis[i][j])
				dfs(i, j);

			cnt[i][j]=(N/modX+(N%modX>i))*(N/modY+(N%modY>j));
		}

	if(time[(tarX*tarX+offX)%modX][(tarY*tarY+offY)%modY]==-1)
		period=-1;
	else
		period=time[(tarX*tarX+offX)%modX][(tarY*tarY+offY)%modY]+1;

	for(i=0;i<modX;++i)
		for(j=0;j<modY;++j)
			update(i, j);

	for(i=0;i<=M;++i)
		if(answers[i])
			fprintf(g, "%d %lld\n", i, answers[i]);

	fclose(f);
	fclose(g);
	return 0;
}