fork(1) download
copy 
  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
comments (?)
stdin
copy 
5
1 1 4 1 1
stdout
copy 
11000
https://ideone.com/rgmJZC
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!