Codeforces Round 860 (Div. 2) - D. Shocking Arrangement (1600)

D. Shocking Arrangement

모두 $0$이면 불가능하다.

그렇지 않다면 항상 가능하다. 가장큰것과 가장 작은것의 차이를 $k$라고 하고, 가장 절댓값이 큰 원소를 $a_x$라고 하자.

$\vert a_x \vert < k$ 이다. 항상 양수와 음수가 있기 때문이다.

처음에 $a_x$를 써준다. 계속 구간합을 관리하며 현재 합이 $0$ 이상이면 음수를 쓰고 반대라면 양수를 쓴다.

구간합은 $\sum^{R}a_i-\sum^{L-1} a_i$ 임을 고려한다.

현재까지의 구간합은 항상 가장큰 양수 이하이다.

지금까지의 구간합중 가장 작은것은 가장작은 음수 이상이다.

따라서 이 두개의 차가 $k$ 보다 커질일이 없기 때문이다.

void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   vi p, m;
   for (int i: a) {
      if (i > 0) p.pb(i);
      else if (i < 0)m.pb(i);
   }
   if (sz(p) + sz(m) == 0) {
      cout << "no\n";
      return;
   }
   sort(all(p));
   sort(all(m));
   int mx = p.back() - m[0];
   reverse(all(p));
   vi ans;
   int pi = 0, mi = 0;
   int v = 0;
   for (int i = 0; i < sz(p) + sz(m); i++) {
      if (pi < sz(p) && v + p[pi] < mx) {
         ans.pb(p[pi]);
         v += p[pi++];
      } else {
         ans.pb(m[mi]);
         v += m[mi++];
      }
   }
   while (sz(ans) < n) ans.pb(0);
   cout << "yes\n";
   for (int i: ans) cout << i << ' ';
   cout << endl;
}