fork download
copy 
  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
comments (?)
stdin
copy 
5
1 1 4 1 1
stdout
copy 
11000
https://ideone.com/qFsDYD
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!