Advertisement
Guest User

Untitled

a guest
Dec 22nd, 2014
153
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.47 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int n;
  7. vector <bool> a;
  8. vector <int> p(0), g(0);
  9. vector <pair <int, int> > res(0);
  10.  
  11. int main()
  12. {
  13. scanf("%d", &n);
  14. a.assign(n, false);
  15. for (int i = 0; i < n; ++i)
  16. {
  17. int x;
  18. scanf("%d", &x);
  19. if (x == 2)
  20. {
  21. a[x] = true;
  22. g.push_back(i);
  23. }
  24. else
  25. p.push_back(i);
  26. }
  27. p.push_back(n);
  28. g.push_back(n);
  29.  
  30. for (int t = 1; t < n; ++t)
  31. {
  32. bool success = true;
  33. int p_s = 0, g_s = 0, p_i = 0, g_i = 0;
  34. while (p[p_i] < n || g[g_i] < n)
  35. {
  36. if (p_i + t >= p.size())
  37. {
  38. if (g_i + t >= g.size())
  39. {
  40. success = false;
  41. break;
  42. }
  43. g_i += t;
  44. ++g_s;
  45. int x = lower_bound(p.begin(), p.end(), g[g_i]) - p.begin();
  46. --x;
  47. if (x >= 0 && x < p.size())
  48. {
  49. p_i = max(p_i, x);
  50. }
  51. break;
  52. }
  53.  
  54. if (g_i + t >= g.size())
  55. {
  56. p_i += t;
  57. ++p_s;
  58. int x = lower_bound(g.begin(), g.end(), p[p_i]) - g.begin();
  59. --x;
  60. if (x >= 0 && x < g.size())
  61. {
  62. g_i = max(g_i, x);
  63. }
  64. break;
  65. }
  66.  
  67. if (p[p_i + t] < g[g_i + t])
  68. {
  69. p_i += t;
  70. ++p_s;
  71. int x = lower_bound(g.begin(), g.end(), p[p_i]) - g.begin();
  72. --x;
  73. if (x >= 0 && x < g.size())
  74. {
  75. g_i = max(g_i, x);
  76. }
  77. }
  78. else
  79. {
  80. g_i += t;
  81. ++g_s;
  82. int x = lower_bound(p.begin(), p.end(), g[g_i]) - p.begin();
  83. --x;
  84. if (x >= 0 && x < p.size())
  85. {
  86. p_i = max(p_i, x);
  87. }
  88. }
  89. }
  90.  
  91. if (success && p_s != g_s)
  92. res.push_back(make_pair(max(p_s, g_s), t));
  93. }
  94.  
  95. sort(res.begin(), res.end());
  96. printf("%d\n", res.size());
  97. for (int i = 0; i < res.size(); ++i)
  98. printf("%d %d\n", res[i].first, res[i].second);
  99.  
  100. return 0;
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement