Cod sursa(job #1046176)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 2 decembrie 2013 18:46:08
Problema Robotei Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define pii pair<int, int>
using namespace std;
int n, m, X, Y, modX, modY, offsetX, offsetY;
int sol[667000];
int Next[1010000], dist[1010000], cycle_len;
vector <int> GT[1010000];
queue <int> Q;
bool Skip, uz[1010000];

inline void Read()
{
	ifstream fin("robotei.in");
	fin >> n >> m >> X >> Y >> modX >> modY >> offsetX >> offsetY;
	fin.close();
	if(X >= modX || Y >= modY)
	{
		if(X < n && Y <n)
		{
			sol[0] = n * n - 1;
			sol[1] = 1;
		}
		else
			sol[0] = n * n;
		Skip = true;
	}
}

inline int Code(int x, int y)
{
	// codifica o pozitie
	return x * modY + y;
}

inline pii Decode(int code)
{
	// decodifica o pozitie
	return make_pair(code / modY, code % modY);
}

inline void BuildGraph()
{
	int i, j, c;
	for(i = 0; i < modX; ++i)
	{
		for(j = 0; j < modY; ++j)
		{
			c = Code(i, j);
			// graful normal - fiecare nod are gradul de iesire 1
			Next[c] = Code((i * i + offsetX) % modX, (j * j + offsetY) % modY);
			// graful transpus
			GT[Next[c]].push_back(c);
		}
	}
}

inline void GetDistances()
{
	// gaseste distantele de la fiecare pozitie la (X, Y)
	int i, j, c, now;
	vector <int>::iterator it;
	for(i = 0; i < modX; ++i)
	{
		for(j = 0; j < modY; ++j)
		{
			c = Code(i, j);
			dist[c] = 1000000000;
		}
	}
	now = Code(X, Y);
	dist[now] = 0;
	Q.push(now);
	while(!Q.empty())
	{
		now = Q.front();
		Q.pop();
		uz[now] = false;
		for(it = GT[now].begin(); it != GT[now].end(); ++it)
		{
			if(dist[*it] > dist[now] + 1)
			{
				dist[*it] = dist[now] + 1;
				if(!uz[*it])
				{
					uz[*it] = true;
					Q.push(*it);
				}
			}
		}
	}
}

inline void GetCycleLength()
{
	// gaseste lungimea ciclului din care face parte (X, Y)
	int c = Code(X, Y);
	cycle_len = dist[Next[c]] + 1;
}

inline void Solve()
{
	int i, j, c, nr, robotei;
	for(i = 0; i < modX; ++i)
	{
		for(j = 0; j < modY; ++j)
		{
			// iau in calcul doar punctele din dreptunghiul modX x modY
			c = Code(i, j);
			if(dist[c] <= m)
			{
				nr = (m - dist[c]) / cycle_len + 1;
				sol[nr]++;
			}
			else
				sol[0]++;
			// iau in calcul doar punctele din afara dreptunghiului modX x modY
			robotei = ((n - 1 - i) / modX + 1) * ((n - 1 - j) / modY + 1) - 1;
			c = Code(i, j);
			c = Next[c];
			if(dist[c] + 1 <= m)
			{
				nr = (m - dist[c] - 1) / cycle_len + 1;
				sol[nr] += robotei;
			}
			else
				sol[0] += robotei;
		}
	}
}

inline void Write()
{
	int i;
	ofstream fout("robotei.out");
	for(i = 0; i <= m; ++i)
		if(sol[i])
			fout << i << ' ' << sol[i] << "\n";
	fout.close();
}

int main()
{
	Read();
	if(!Skip)
	{
		BuildGraph();
		GetDistances();
		GetCycleLength();
		Solve();
	}
	Write();
	return 0;
}