C++(g++ 7.5.0) 解法, 执行用时: 455ms, 内存消耗: 45052K, 提交时间: 2023-05-18 22:05:52

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+7,INF = 1e9+7;
#define int long long
int n,d;
int a[N],c[N],v[N],v1[N];
int ans1,p1,ans2,p2;
void clear(){
    for(int i=1;i<=n;i++) c[a[i]]--;
}
void sft(int i){
    int x = a[i],t = c[x];
    for(int j=0;j<t;j++) v[i+j*d] = x;
    int now = 1;
    for(int j=1;j<=n;j++){
        if(a[j] == x) j += t;
        while(now <= n && v[now] == x) now++;
        if(now <= n) v[now++] = a[j];
    }
}
void sft1(int i){
    int x = a[i],t = c[x];
    for(int j=0;j<t;j++) v1[n-j*d] = x;
    int now = 1;
    for(int j=1;j<=n;j++){
        if(a[j] == x) j += t;
        while(now <= n && v1[now] == x) now++;
        if(now <= n) v1[now++] = a[j];
    }
}
void prt(){
    for(int i=1;i<=n;i++) cout << v[i] << " \n"[i==n];
}
void prt1(){
    for(int i=1;i<=n;i++) cout << v1[i] << " \n"[i==n];
}
void solve(){
    cin >> n >> d;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        v[i] = v1[i] = 0;
        c[a[i]]++;
    }
    sort(a+1,a+1+n);
    ans1 = p1 = ans2 = p2 = 0;
    bool flag = false;
    for(int i=1;i<=n;i+=c[a[i]]){
        int t = c[a[i]];
        if(t == 1){
            flag = true;
            break;
        }
        int r = i + (t-1)*d, le = n - (t-1) * d;
        if(r <= n){
            ans1 = i;
        }
        else if(le > 0 && le > p2){
            p2 = le,ans2 = i;
        }
    }
    if(flag || d==1){
        for(int i=1;i<=n;i++) cout << a[i] << " \n"[i==n];
        clear(); return;
    }
    if(!ans1 && !ans2){
        cout << "-1\n";
        clear(); return;
    }
    //cout << ans1 << ' ' << ans2 << '\n';
    if(ans1) sft(ans1);
    if(ans2) sft1(ans2);
    if(ans1 && !ans2){
        prt();
        clear();
        return;
    }
    if(!ans1 && ans2){
        prt1();
        clear();
        return;
    }
    flag = true;
    for(int i=1;i<=n;i++){
        if(v[i] == v1[i]) continue;
        if(v[i] > v1[i]) flag = false;
        break;
    }
    if(flag){
        prt();
        clear();
    }
    else{
        prt1();
        clear();
    }
}
signed main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
/*
1
7 3
1 1 2 2 2 3 3
 */

C++ 解法, 执行用时: 378ms, 内存消耗: 14884K, 提交时间: 2022-07-08 16:52:41

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[1000005];
int mp[1000005];
int c[1000005];
int ans[1000005];
void solve(){
	int n,d,m=0,cnt=0;
	scanf("%d%d",&n,&d);
	mp[0]=n+10;
	for(int i=1;i<=n;i++)
		mp[i]=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		mp[a[i]]++;
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		if(mp[a[i]]==1){
			for(int j=1;j<=n;j++)
				printf("%d ",a[j]);
			puts("");
			return;
		}
	}
	int now=0,z=0,loc=0,now1=0,m1;
	for(int i=n;i>=1;i--){
		int t=i;
		if(a[i]!=a[i-1]&&mp[a[i]]<=mp[z]){z=a[i];t++;}
		if((mp[z]-1)*d+1<=n-i+1&&t>=loc){
			if(!now){now=i;m=z;loc=t;}
			else{now1=i;m1=z;break;}
		}
	}
	if(loc==0){puts("-1");return;}
	if(now1){
		for(int i=1;i<=n;i++)
			ans[i]=a[i];
		cnt=0;
		for(int i=now1;i<=n;i++)
			if(a[i]!=m1)c[++cnt]=a[i];
		cnt=0;
		for(int i=now1;i<=n;i++)
			if((i-now1)%d==0&&mp[m1]){ans[i]=m1;mp[m1]--;}
			else ans[i]=c[++cnt];
	}
	cnt=0;
	for(int i=now;i<=n;i++)
		if(a[i]!=m)c[++cnt]=a[i];
	cnt=0;
	for(int i=now;i<=n;i++)
		if((i-now)%d==0&&mp[m]){a[i]=m;mp[m]--;}
		else a[i]=c[++cnt];
	int p=1;
	if(now1){
		for(int i=1;i<=n;i++)
			if(ans[i]>a[i])break;
			else if(a[i]>ans[i]){p=0;break;}
	}
	for(int i=1;i<=n;i++)
		if(p)
			printf("%d ",a[i]);
		else printf("%d ",ans[i]);
	puts("");
    return;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--)solve();
	return 0;
}