fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ii pair <int, int>
  3. #define ll long long
  4. #define llll pair <ll, ll>
  5. #define ld long double
  6. #define el "\n"
  7. #define sp " "
  8. #define fi first
  9. #define se second
  10. #define pub push_back
  11. #define puf push_front
  12. #define pob pop_back
  13. #define pof pop_front
  14. #define __lcm(a, b) (a / __gcd(a, b) * b)
  15. #define sq(x) (x) * (x)
  16. #define sz(a) (int)(a.size())
  17. using namespace std;
  18.  
  19. const int INFI = 1e9 + 7; const ll INFL = 2e18 + 7;
  20.  
  21. int n;
  22. ll a[10005], b[10005], c[10005];
  23. bool vi[10005];
  24.  
  25. int calc(int x)
  26. {
  27.     return (x - 1 + n) % n + 1;
  28. }
  29.  
  30. void Solve()
  31. {
  32.     cin >> n;
  33.     ll A = 0;
  34.     for (int i = 1; i <= n; i++) 
  35.     {
  36.         cin >> b[i];
  37.         A += b[i];
  38.     }
  39.     A /= 3; //sum of a[i]
  40.     if (n % 3)
  41.     {
  42.         ll C = 0;
  43.         int i = calc(1 + 3);
  44.         vi[1] = 1;
  45.         while (true)
  46.         {
  47.             if (vi[i]) break;
  48.             vi[i] = 1;
  49.             c[i] = b[calc(i - 1)] - b[calc(i - 2)] + c[calc(i - 3)];
  50.             C += c[i]; //sum of c[i]
  51.             i = calc(i + 3);
  52.         }
  53.         a[1] = (A - C) / n;
  54.         for (int i = 2; i <= n; i++) a[i] = a[1] + c[i];
  55.     }
  56.     else
  57.     {
  58.         ll delta = -INFL;
  59.         for (int i = 4; i <= n; i += 3) 
  60.         {
  61.             a[i] = b[i - 1] - b[i - 2] + a[i - 3];
  62.             delta = max(delta, -a[i]);
  63.         }
  64.         for (int i = 1; i <= n; i += 3) a[i] += max((ll)0, delta) + 1;
  65.         delta = -INFL;
  66.         for (int i = 5; i <= n; i += 3) 
  67.         {
  68.             a[i] = b[i - 1] - b[i - 2] + a[i - 3];
  69.             delta = max(delta, -a[i]);
  70.         }
  71.         for (int i = 2; i <= n; i += 3) a[i] += max((ll)0, delta) + 1;
  72.         for (int i = 3; i <= n; i += 3) a[i] = b[i - 1] - a[i - 1] - a[i - 2];
  73.     }
  74.     for (int i = 1; i <= n; i++) cout << a[i] << sp;
  75. }
  76.  
  77. int main()
  78. {
  79.     ios_base::sync_with_stdio(0);  cin.tie(NULL);  cout.tie(0);
  80.     freopen("Vong so.inp", "r", stdin);
  81.     freopen("Vong so.out", "w", stdout);
  82.     Solve();
  83.     return 0;
  84. }
  85.  
  86. //coded by icyalmond
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AUOfQu
language:
C++14 (gcc 8.3)
created:
19 hours 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!