fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int maxn = 100000 + 1;
  6.  
  7. int a[maxn];
  8. int n, m;
  9. int answer[maxn];
  10.  
  11. void prepare () {
  12. //freopen("input.txt", "r", stdin);
  13. //freopen("output.txt", "w", stdout);
  14. }
  15.  
  16. void read () {
  17. scanf("%d", &n);
  18. for (int i = 0; i < n; i++) {
  19. scanf("%d", &a[i]);
  20. }
  21. }
  22.  
  23. void solve_all_zeros() {
  24. for (int i = 0; i < n; i++) {
  25. if (a[i] != 0) return;
  26. }
  27. for (int i = 1; i <= n; i++) {
  28. printf("1");
  29. }
  30. printf("\n");
  31. exit(0);
  32. }
  33.  
  34. void remove_zeros() {
  35. for (int i = 0; i < n; i++) {
  36. if (a[i] == 0) continue;
  37. a[m] = a[i];
  38. m++;
  39. }
  40. }
  41.  
  42. vector<int> get_divisors(int S) {
  43. vector<int> divisors;
  44. for (int k = 1; k * k <= S; k++) {
  45. if (S % k == 0) {
  46. divisors.push_back(k);
  47. if (S / k != k) {
  48. divisors.push_back(S / k);
  49. }
  50. }
  51. }
  52. return divisors;
  53. }
  54.  
  55. bool can_divide(int need_sum) {
  56. vector<int> next(m), dp(m);
  57. int current_sum = 0;
  58. int left_iterator = 0;
  59. int right_iterator = 0;
  60. while (left_iterator < m) {
  61. while (right_iterator < m && current_sum < need_sum) {
  62. current_sum += a[right_iterator];
  63. right_iterator++;
  64. }
  65. if (current_sum == need_sum) {
  66. next[left_iterator] = right_iterator - 1;
  67. } else {
  68. next[left_iterator] = -1;
  69. }
  70. current_sum -= a[left_iterator];
  71. left_iterator++;
  72. }
  73.  
  74. for (int i = m - 1; i >= 0; i--) {
  75. if (next[i] == -1) {
  76. dp[i] = i;
  77. } else {
  78. if (next[i] + 1 < m) {
  79. dp[i] = dp[next[i] + 1];
  80. } else {
  81. dp[i] = m;
  82. }
  83. }
  84. }
  85.  
  86. current_sum = 0;
  87. left_iterator = 0;
  88. right_iterator = m - 1;
  89. while (right_iterator >= 0 && current_sum < need_sum) {
  90. current_sum += a[right_iterator];
  91. right_iterator--;
  92. }
  93. while (left_iterator < m) {
  94. current_sum += a[left_iterator];
  95. left_iterator++;
  96. while (right_iterator < m - 1 && current_sum > need_sum) {
  97. right_iterator++;
  98. current_sum -= a[right_iterator];
  99. }
  100. if (current_sum < need_sum) continue;
  101. if (current_sum > need_sum) break;
  102. if (dp[left_iterator] == right_iterator + 1) {
  103. return true;
  104. }
  105. }
  106. return false;
  107. }
  108.  
  109. void solve () {
  110. solve_all_zeros();
  111. remove_zeros();
  112. int sum = 0;
  113. for (int i = 0; i < m; i++) {
  114. sum += a[i];
  115. }
  116. vector<int> divisors = get_divisors(sum);
  117. for (int divisor : divisors) {
  118. if (sum / divisor > n) continue;
  119. if (divisor == sum) {
  120. answer[sum / divisor] = 1;
  121. } else {
  122. if (can_divide(divisor)) {
  123. answer[sum / divisor] = 1;
  124. }
  125. }
  126. }
  127. for (int i = 1; i <= n; i++) {
  128. printf("%d", answer[i]);
  129. }
  130. printf("\n");
  131. }
  132.  
  133. int main () {
  134.  
  135. prepare();
  136. read();
  137. solve();
  138.  
  139. return 0;
  140. }
Success #stdin #stdout 0s 4456KB
stdin
5
1 1 4 1 1
stdout
11000