Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Problem: E. Singers' Tour
- // Contest: Codeforces - Codeforces Round 760 (Div. 3)
- // URL: https://codeforces.com/problemset/problem/1618/E
- // Memory Limit: 256 MB
- // Time Limit: 2000 ms
- //
- // Powered by CP Editor (https://cpeditor.org)
- #include <assert.h>
- #include <bits/stdc++.h>
- using namespace std;
- #ifndef __DEBUG__
- #define dbg(...) 42
- #endif
- template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
- using ll = long long;
- using a2l = array<ll, 2>;
- using pll = pair<ll, ll>;
- using vl = vector<ll>;
- void solve()
- {
- ll n;
- cin >> n;
- vl bs(n);
- for (auto &x : bs)
- cin >> x;
- vl as(n), cs(n), vs(n);
- for (ll i = 0; i < n; ++i)
- as[i] = bs[i] - bs[(i - 1 + n) % n];
- for (ll i = 0; i < n; ++i)
- cs[i] = as[i] - as[(i - 1 + n) % n];
- for (auto x : cs) {
- if (x % n) {
- dbg(x);
- cout << "NO\n";
- return;
- }
- }
- for (ll i = 1; i < n; ++i)
- vs[i] = vs[i - 1] - cs[i] / n;
- ll final = 0, factor = n * (n + 1) / 2;
- for (ll i = 0; i < n; ++i)
- final += ((n - i) % n + 1) * vs[i];
- if ((final - bs[0]) % factor) {
- dbg(final, bs[0], factor);
- cout << "NO\n";
- return;
- }
- ll d = (final - bs[0]) / factor;
- for (ll i = 0; i < n; ++i) {
- vs[i] -= d;
- if (vs[i] <= 0) {
- dbg(vs[i]);
- cout << "NO\n";
- return;
- }
- }
- cout << "YES\n";
- for (auto x : vs)
- cout << x << ' ';
- cout << '\n';
- }
- int main(int argc, char **argv)
- {
- ll t;
- cin >> t;
- while (t--)
- solve();
- return 0;
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement