fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define fo(i, n) for(int i = 1; i <= n; ++i)
  7.  
  8. typedef long long ll;
  9.  
  10. const int N = 500500;
  11. const int mod = 1e9 + 7;
  12.  
  13. int n, s, a[N];
  14. vector<int> d;
  15. int ans[N], dp[N];
  16. inline int solve(int k) {
  17.     int one = s / k, curs = 0, res = 0;
  18.     dp[0] = 0;
  19.     int l = 0, sl = 0;
  20.     for(int i = 1; i <= n; ++i)  {
  21.         curs += a[i];
  22.         while(sl + one < curs) sl += a[++l];
  23.         if(sl + one == curs) {
  24.             dp[i] = dp[l] + 1;
  25.             if(i < n && dp[i] + 1 == k) return 1;
  26.         } else dp[i] = 0;
  27.     }
  28.     return dp[n] == k;
  29. }
  30.  
  31. int main() {
  32.  
  33.     ios::sync_with_stdio(0); cin.tie(0);
  34.     cin >> n;
  35.     fo(i, n) cin >> a[i], s += a[i];
  36.     if(s == 0) {
  37.         fo(i, n) cout << 1;
  38.         return 0;
  39.     }
  40.     fo(i, n) a[i + n] = a[i];
  41.     for(int i = 1; i * i <= s; ++i)
  42.         if(s % i == 0) {
  43.             if(i <= n) d.pb(i);
  44.             if(i * i != s && s / i <= n) d.pb(s / i);
  45.         }
  46.     for(int k : d) {
  47.         ans[k] = solve(k);
  48.     }
  49.     fo(i, n) cout << ans[i];
  50.     return 0;
  51. }
Success #stdin #stdout 0s 4480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AK3UU4
language:
C++14 (gcc 8.3)
created:
6 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!