Íŕçŕä ę ëó÷řčě đĺřĺíč˙ě Status: AC, problem ZFIRM, contest ZEL07. By dale (Alexey Danchenko), 2007-02-17 21:33:10.
#include <stdio.h>
 
int main()
{
	int n;
	scanf("%d", &n);
	int a[5005], b[5005];
	int i;
	for (i= 0; i < n; ++i)
	{
		int j;
		scanf("%d", &j);
		--j;
		a[j] = i;
		b[a[j]] = j;
	}
 
	int zero = 1;
	for (i = 0; i < n; ++i)
		if (a[i] != i) { zero = 0; break; }
	if (zero)
	{
		printf("0\n");
		return 0;
	}
 
	int one = 1;
	int cnt = 0;
	for (i = 0; i < n; ++i)
	{
		if (a[i] != i && a[a[i]] != i) { one = 0; break; }
		if (a[a[i]] == i && i < a[i]) ++cnt;
	}
 
	if (one)
	{
		printf("1\n");
		printf("%d", cnt);
		for (i = 0; i < n; ++i)
		{
			if (a[a[i]] == i && i < a[i])
				printf(" %d-%d", i+1, a[i]+1);
		}
		printf("\n");
		return 0;
	}
 
	printf("2\n");
	int was[5005] = {0};
	int p[5005][2];
	int cntp = 0;
	for (i = 0; i < n; ++i)
		if (was[i] == 0 && i != a[i])
		{
			was[i] = 1;
			if (i == a[a[i]])
			{
				was[a[i]] = 1;
				p[cntp][0] = i;
				p[cntp][1] = a[i];
				++cntp;
				int z = a[i];
				int t = a[i]; a[i] = a[z]; a[z] = t;
			}
			else 
			{
				int j = i;
				while (was[a[j]] == 0)
				{
					was[a[j]] = 1;
					if  (a[j] == j || a[a[j]] == j) break;
					int k = b[j];
					p[cntp][0] = a[j];
					p[cntp][1] = k;
					++cntp;
					b[j] = a[j];
					b[a[a[j]]] = k;
					int t = a[a[j]]; a[a[j]] = a[k]; a[k] = t;
					was[k] = 1;
					j = k;
				}
			}
		}
	printf("%d", cntp);
	for (i = 0; i < cntp; ++i)
		printf(" %d-%d", p[i][0]+1, p[i][1]+1);
 
	cnt = 0;
	for (i = 0; i < n; ++i)
	{
		if (a[a[i]] == i && i < a[i]) ++cnt;
	}
	printf("\n%d", cnt);
	for (i = 0; i < n; ++i)
	{
		if (a[a[i]] == i && i < a[i]) printf(" %d-%d", i+1, a[i]+1);
	}
	printf("\n");
	return 0;
}