fork(1) download
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <string>
  4. #include <functional>
  5. #include <cassert>
  6. #include <cstdlib>
  7.  
  8. std::string solve(const std::vector<int>& a) {
  9. const int n = a.size();
  10. int sum = 0;
  11. for (auto& it : a) {
  12. assert(it >= 0);
  13. sum += it;
  14. }
  15. assert(0 <= sum && sum <= 1e9);
  16. if (sum == 0) {
  17. return std::string(n, '1');
  18. }
  19. std::function<bool(int)> is_possible = [&](int number) {
  20. const int need_sum = sum / number;
  21. assert(need_sum * number == sum);
  22. // Найдем такой отрезок [l, r), (0 <= l < r < n), сумма в котором равна need_sum:
  23. int r = 0, l = 0, curr_sum = 0, rem = sum;
  24. while (l < n) {
  25. while (r < n && curr_sum + a[r] <= need_sum) {
  26. curr_sum += a[r];
  27. ++r;
  28. }
  29. if (curr_sum == need_sum) {
  30. break;
  31. }
  32. curr_sum -= a[l];
  33. ++l;
  34. }
  35. if (curr_sum != need_sum) {
  36. return false;
  37. }
  38. rem -= need_sum;
  39. assert(0 <= l && l < r && r <= n);
  40. // Найдем все оставшиеся отрезки:
  41. --number, curr_sum = 0;
  42. int i = r % n;
  43. while (i != l) {
  44. curr_sum += a[i];
  45. if (curr_sum > need_sum) {
  46. return false;
  47. } else if (curr_sum == need_sum) {
  48. --number;
  49. rem -= need_sum;
  50. curr_sum = 0;
  51. }
  52. ++i;
  53. if (i >= n) {
  54. i -= n;
  55. }
  56. }
  57. assert(rem == 0 && number == 0 && curr_sum == 0);
  58. return true;
  59. };
  60.  
  61. std::string answ(n, '0');
  62.  
  63. for (int i = 1; i * i <= sum; ++i) {
  64. const int j = sum / i;
  65. if (j * i == sum) {
  66. if (i <= n) {
  67. assert(answ[i-1] == '0');
  68. answ[i-1] += is_possible(i);
  69. }
  70. if (j <= n && j != i) {
  71. assert(answ[j-1] == '0');
  72. answ[j-1] += is_possible(j);
  73. }
  74. }
  75. }
  76. assert(answ[0] == '1');
  77. return answ;
  78. }
  79.  
  80. int main() {
  81. int n;
  82. scanf("%d", &n);
  83. std::vector<int> a(n);
  84. for (auto& it : a) {
  85. scanf("%d", &it);
  86. }
  87. printf("%s\n", solve(a).c_str());
  88. return 0;
  89. }
Success #stdin #stdout 0s 4184KB
stdin
5
1 1 4 1 1
stdout
11000