Назад к лучшим решениям Status: AC, problem ZFIRM, contest ZEL07. By dale (Alexey Danchenko), 2007-02-17 21:33:10.
  1. #include <stdio.h>
  2.  
  3. int main()
  4. {
  5. int n;
  6. scanf("%d", &n);
  7. int a[5005], b[5005];
  8. int i;
  9. for (i= 0; i < n; ++i)
  10. {
  11. int j;
  12. scanf("%d", &j);
  13. --j;
  14. a[j] = i;
  15. b[a[j]] = j;
  16. }
  17.  
  18. int zero = 1;
  19. for (i = 0; i < n; ++i)
  20. if (a[i] != i) { zero = 0; break; }
  21. if (zero)
  22. {
  23. printf("0\n");
  24. return 0;
  25. }
  26.  
  27. int one = 1;
  28. int cnt = 0;
  29. for (i = 0; i < n; ++i)
  30. {
  31. if (a[i] != i && a[a[i]] != i) { one = 0; break; }
  32. if (a[a[i]] == i && i < a[i]) ++cnt;
  33. }
  34.  
  35. if (one)
  36. {
  37. printf("1\n");
  38. printf("%d", cnt);
  39. for (i = 0; i < n; ++i)
  40. {
  41. if (a[a[i]] == i && i < a[i])
  42. printf(" %d-%d", i+1, a[i]+1);
  43. }
  44. printf("\n");
  45. return 0;
  46. }
  47.  
  48. printf("2\n");
  49. int was[5005] = {0};
  50. int p[5005][2];
  51. int cntp = 0;
  52. for (i = 0; i < n; ++i)
  53. if (was[i] == 0 && i != a[i])
  54. {
  55. was[i] = 1;
  56. if (i == a[a[i]])
  57. {
  58. was[a[i]] = 1;
  59. p[cntp][0] = i;
  60. p[cntp][1] = a[i];
  61. ++cntp;
  62. int z = a[i];
  63. int t = a[i]; a[i] = a[z]; a[z] = t;
  64. }
  65. else
  66. {
  67. int j = i;
  68. while (was[a[j]] == 0)
  69. {
  70. was[a[j]] = 1;
  71. if (a[j] == j || a[a[j]] == j) break;
  72. int k = b[j];
  73. p[cntp][0] = a[j];
  74. p[cntp][1] = k;
  75. ++cntp;
  76. b[j] = a[j];
  77. b[a[a[j]]] = k;
  78. int t = a[a[j]]; a[a[j]] = a[k]; a[k] = t;
  79. was[k] = 1;
  80. j = k;
  81. }
  82. }
  83. }
  84. printf("%d", cntp);
  85. for (i = 0; i < cntp; ++i)
  86. printf(" %d-%d", p[i][0]+1, p[i][1]+1);
  87.  
  88. cnt = 0;
  89. for (i = 0; i < n; ++i)
  90. {
  91. if (a[a[i]] == i && i < a[i]) ++cnt;
  92. }
  93. printf("\n%d", cnt);
  94. for (i = 0; i < n; ++i)
  95. {
  96. if (a[a[i]] == i && i < a[i]) printf(" %d-%d", i+1, a[i]+1);
  97. }
  98. printf("\n");
  99. return 0;
  100. }