解法は2つある． いずれにせよ，まずは 1周を一塊で考える．
解法0: Binary search
\(K\) を固定する．(\(m\) 周できるか) \(\in Bool\) は単調．
\(m\) 周すると，各 \(i \in N\) に対して \(min(a_{i},m)\) 個食べるので， その合計が \(K\) 以下かどうかで判定できる．
判定に \(O(N)\), binary search に \(O(log\,K)\)．
解法1: シュミレーション, min priority queue
1周単位で考えるのは同じだが，高速化のためにまとめて周回する． \(a\) の内，\(0\) より真に大きい元の min だけ周回する． ただし，\(K\) が小さいときにはそれができないので， そのときは可能な限り食べた後に，端数分は個別に計算．
まとめて食べる作業が \(O(N)\), 端数の計算が \(O(N)\), \(min_{i} \{a_{i} \, \vert \, a_{i} \neq 0 \}\) を取り出すために min priority queue を用いると \(O(log \,N)\)．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
// binary search
int main() {
ll n, k ;
cin >> n >> k;
vll a(n); rep(i,n) { cin >> a[i]; }
ll ok, ng;
ok = 0, ng = k+10;
while(abs(ok-ng) > 1){
ll md = (ok + ng)/2;
ll cnt = 0;
rep(i,n){
cnt += min(a[i], md);
}
if(cnt <= k) ok = md;
else ng = md;
}
rep(i,n){
ll x = max(a[i]-ok, 0LL);
k -= a[i] - x;
a[i] = x;
}
assert( k >= 0 );
rep(i,n) if(k > 0 && a[i] > 0){
a[i]--;
k--;
}
assert(k == 0);
rep(i,n) cout << a[i] << endl;
return 0;
}
// min priority queue
int main() {
ll n, k ;
cin >> n >> k;
vll a(n); rep(i,n) { cin >> a[i]; }
min_priority_queue<ll> q;
rep(i,n) q.push(a[i]);
ll s_cyc = 0;
rep(i,n){
ll mi = q.top();
mi -= s_cyc;
if(mi <= 0) { q.pop(); continue; }
if(k < q.size()) break;
ll cyc = 0;
if(q.size()*mi <= k){
cyc = mi;
} else{
cyc += k/q.size();
}
s_cyc += cyc;
k -= cyc*q.size();
q.pop();
}
rep(i,n){
a[i] -= s_cyc;
chmax(a[i], 0LL);
if(k > 0 && a[i] > 0) {
a[i]--;
k--;
}
cout << a[i] << endl;
}
assert(k == 0);
return 0;
}
