Advertisement
pb_jiang

CF1618E

Mar 23rd, 2025
350
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.67 KB | None | 0 0
  1. // Problem: E. Singers' Tour
  2. // Contest: Codeforces - Codeforces Round 760 (Div. 3)
  3. // URL: https://codeforces.com/problemset/problem/1618/E
  4. // Memory Limit: 256 MB
  5. // Time Limit: 2000 ms
  6. //
  7. // Powered by CP Editor (https://cpeditor.org)
  8.  
  9. #include <assert.h>
  10. #include <bits/stdc++.h>
  11. using namespace std;
  12. #ifndef __DEBUG__
  13. #define dbg(...) 42
  14. #endif
  15. template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
  16.  
  17. using ll = long long;
  18. using a2l = array<ll, 2>;
  19. using pll = pair<ll, ll>;
  20. using vl = vector<ll>;
  21.  
  22. void solve()
  23. {
  24.     ll n;
  25.     cin >> n;
  26.     vl bs(n);
  27.     for (auto &x : bs)
  28.         cin >> x;
  29.     vl as(n), cs(n), vs(n);
  30.     for (ll i = 0; i < n; ++i)
  31.         as[i] = bs[i] - bs[(i - 1 + n) % n];
  32.     for (ll i = 0; i < n; ++i)
  33.         cs[i] = as[i] - as[(i - 1 + n) % n];
  34.     for (auto x : cs) {
  35.         if (x % n) {
  36.             dbg(x);
  37.             cout << "NO\n";
  38.             return;
  39.         }
  40.     }
  41.     for (ll i = 1; i < n; ++i)
  42.         vs[i] = vs[i - 1] - cs[i] / n;
  43.     ll final = 0, factor = n * (n + 1) / 2;
  44.     for (ll i = 0; i < n; ++i)
  45.         final += ((n - i) % n + 1) * vs[i];
  46.     if ((final - bs[0]) % factor) {
  47.         dbg(final, bs[0], factor);
  48.         cout << "NO\n";
  49.         return;
  50.     }
  51.     ll d = (final - bs[0]) / factor;
  52.     for (ll i = 0; i < n; ++i) {
  53.         vs[i] -= d;
  54.         if (vs[i] <= 0) {
  55.             dbg(vs[i]);
  56.             cout << "NO\n";
  57.             return;
  58.         }
  59.     }
  60.     cout << "YES\n";
  61.     for (auto x : vs)
  62.         cout << x << ' ';
  63.     cout << '\n';
  64. }
  65.  
  66. int main(int argc, char **argv)
  67. {
  68.     ll t;
  69.     cin >> t;
  70.     while (t--)
  71.         solve();
  72.     return 0;
  73. };
  74.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement