CF2167E题解

#include<bits/stdc++.h>
#define int long long
#define ft first
#define sd second
using namespace std;
int read(){
	int cnt = 0, sign = 1;
	char c = getchar();
	while(!isdigit(c)){
		if(c == '-')	sign = -1;
		c = getchar();
	}
	while(isdigit(c)){
		cnt = (cnt << 1) + (cnt << 3) + (c ^ 48);
		c = getchar();
	}
	return cnt * sign;
}
const int N = 2e5 + 10;
int a[N]; 
signed main(){
	int T = read();
	while(T--){
		int n = read(), k = read(), x = read();
		for(int i = 1; i <= n; i++){
			a[i] = read();
		}
		sort(a + 1, a + n + 1);
		int l = 0, r = x + 2;
		while(l <= r){
			int mid = (l + r) >> 1;
			vector < pair <int, int> > vec;
			for(int i = 1; i <= n; i++){
				int lt = max(a[i] - mid + 1, 0ll);
				int rt = min(a[i] + mid - 1, x * 1ll);
				if(lt <= rt)	vec.push_back({lt, rt});
			}
			sort(vec.begin(), vec.end());
			vector < pair <int, int> > mer;
			for(auto &t : vec){
				if(mer.empty() || t.ft > mer.back().sd + 1){
					mer.push_back(t);
				}else{
					mer.back().sd = max(mer.back().sd, t.sd);
				}
			}
			int sum = 0;
			for(auto &t : mer){
				sum += (t.sd - t.ft + 1);
			}
			if(x + 1 - sum >= k){
				l = mid + 1;
			}else{
				r = mid - 1;
			}
		}
		vector < pair <int, int> > vec;
		int de = r;
		for(int i = 1; i <= n; i++){
			int lt = max(a[i] - de + 1, 0ll);
			int rt = min(a[i] + de - 1, x * 1ll);
			if(lt <= rt)	vec.push_back({lt, rt});
		}
		sort(vec.begin(), vec.end());
		vector < pair <int, int> > mer;
		for(auto &t : vec){
			if(mer.empty() || t.ft > mer.back().sd + 1){
				mer.push_back(t);
			}else{
				mer.back().sd = max(mer.back().sd, t.sd);
			}
		}
		vector <int> ans;
		int cnt = 0;
		for(auto &t : mer){
			for(int i = cnt; i < t.ft && ans.size() < k; i++){
				ans.push_back(i);
			}
			cnt = t.sd + 1;
			if(ans.size() >= k){
				break;
			}
		}
		if(ans.size() < k){
			for(int i = cnt; i <= x && ans.size() < k; i++){
				ans.push_back(i);
			}
		}
		for(int i = 0; i < k; i++){
			printf("%d ", ans[i]);
		}
		printf("\n");
	}
	return 0;
}