Tikut

input/code.cpp: In function 'int main()':
input/code.cpp:32:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |                 auto [l,u]=rn(1,mb-k);
      |                      ^

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 112345
#define MS 212345
#define CD(a,b) (1+((a)-1)/(b))

int n,m,MM,r[MS],AA[MS];
array<int,N> t;
pair<ll,ll> rn(int a,int b){
	ll L=0,U=0;
	for(int i=0;i<n;++i){
		int u=t[i]/a,l=CD(t[i],b);
		if(a>t[i]||l>u) return {-123,-123};
		U+=u-1;
		L+=l-1;
	}
	return {L,U};
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m;
	for(int i=0;i<n;++i) cin>>t[i];
	for(int i=0;i<m;++i) r[i]=INT_MAX;
	sort(t.begin(),t.begin()+n);
	MM=t[n-1];

	int mb=MM;
	for(int k=1<<30;k;k/=2){
		if(mb-k<1) continue;
		auto [l,u]=rn(1,mb-k);
		if(l<=m&&m<=u) mb-=k;
	}

	set<int> B;
	for(int i=0;i<n;++i){
		for(int k=1;k<=m+1;++k){
			int e=CD(t[i],k);
			if(e>=mb) B.insert(e);
			else break;
		}
	}

	for(auto it=B.begin();it!=B.end();++it){
		int b=*it,a=MM,l=0,bc=0;
		priority_queue<array<int,3>> q;
		for(int i=0;i<n;++i){
			int d=CD(t[i],b);
			if(t[i]/(d+1)){
				q.push({t[i]/(d+1),t[i],d+1});
			}
			if(CD(t[i],d)==b) ++bc;
			l+=CD(t[i],b)-1;
			a=min(a,t[i]/d);
		}
		if(l&&l<=m){
			if(b-a<r[l-1]) AA[l-1]=a;
			r[l-1]=min(r[l-1],b-a);
		}
		for(;l<m&&bc;++l){
			auto z=q.top(); q.pop();
			int d=z[2];
			int e=z[1];
			if(CD(e,(d-1))==b&&CD(e,d)!=b) --bc;
			a=min(a,z[0]);
			if(b-a<r[l]) AA[l]=a;
			r[l]=min(r[l],b-a);
			if(e/(d+1)) q.push({e/(d+1),e,d+1});
		}
	}
	for(int i=0;i<m-1;++i){
		if(AA[i+1]>AA[i]) return 1;
	}
	for(int i=0;i<m;++i) cout<<r[i]<<' ';
	cout<<'\n';
}

Test 1

Group: 1, 3, 4, 5, 6

Verdict: ACCEPTED

Test 2

Group: 1, 4, 5, 6

Verdict: ACCEPTED

Test 3

Group: 1, 4, 5, 6

Verdict: ACCEPTED

Test 4

Group: 1, 4, 5, 6

Verdict: ACCEPTED

Test 5

Group: 2, 5, 6

Verdict: ACCEPTED

Test 6

Group: 2, 5, 6

Verdict: ACCEPTED

Test 7

Group: 3, 5, 6

Verdict: ACCEPTED

Test 8

Group: 3, 5, 6

Verdict: ACCEPTED

Test 9

Group: 3, 5, 6

Verdict: ACCEPTED

Test 10

Group: 3, 5, 6

Verdict: ACCEPTED

Test 11

Group: 3, 5, 6

Verdict: ACCEPTED

Test 12

Group: 4, 5, 6

Verdict: ACCEPTED

Test 13

Group: 4, 5, 6

Verdict: ACCEPTED

Test 14

Group: 4, 5, 6

Verdict: ACCEPTED

Test 15

Group: 4, 5, 6

Verdict: ACCEPTED

Test 16

Group: 5, 6

Verdict: ACCEPTED

Test 17

Group: 5, 6

Verdict: ACCEPTED

Test 18

Group: 5, 6

Verdict: ACCEPTED

Test 19

Group: 5, 6

Verdict: ACCEPTED

Test 20

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 6

Verdict: TIME LIMIT EXCEEDED