提出 #58279635

---

ソースコード 拡げる

/* cmdS
	g++ -std=gnu++17 -O3 -o a "$F"
*/
#include <algorithm>
#include <iostream>

int N,M;
int64_t X,K,A[200000],B[200000],S[200001];
using namespace std;

int main()
{
	cin>>N>>M>>K;
	for (int i = 0; i < N; ++i) {
		cin>>A[i];
		B[i] = A[i];
	}
	sort(B,B+N,greater<int64_t>());

	if (N==M) {
		for (int i = 0; i < N; ++i) {
			cout<<0<<(i==N-1 ? "\n" : " ");
		}
	} else {
		S[0] = 0;
		for (int i = 0; i < N; ++i) {
			S[i+1] = S[i]+B[i];
		}
		X = K-S[N];
		for (int i = 0; i < N; ++i) {
			int64_t a = A[i];
			int k = lower_bound(B,B+N,a,greater<int64_t>())-B;
			int64_t s = (M<=k) ? S[M] : S[M+1]-a;
			auto p = [&](int64_t x){
				int64_t b = a+x+1;
				int k = upper_bound(B,B+N,b,greater<int64_t>())-B;
				k = min(k,M);
				int64_t t = s-S[k]+b*k;
				return X-x < b*M-t;
			};
			if (p(0)) {
				cout<<0<<(i==N-1 ? "\n" : " ");
			} else if (! p(X)) {
				cout<<-1<<(i==N-1 ? "\n" : " ");
			} else {
				int64_t l = 0,r = X;
				while (l+1 < r) {
					int64_t m = l+(r-l)/2;
					if (p(m)) {
						r = m;
					} else {
						l = m;
					}
				}
				cout<<r<<(i==N-1 ? "\n" : " ");
			}
		}
	}
	
	return 0;
}

提出情報

ジャッジ結果