Submission #70829153

---

Source Code Expand

#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define ll long long
#define lb(x) ((x)&(-(x)))
#define Rev reverse
#define all(s) s.begin(),s.end()
using namespace std;
const int N=1e6+10,mod=998244353;
int buc[55];
string s;int n;
int bf[N],id[N];
void slv(){
    for(int i=0;i<26;i++) buc[i]=0;
    cin>>s;n=s.length();
    for(auto ed:s){
        buc[ed-'a']++;
    }
    int mx=0,mxid=0;
    for(int i=0;i<26;i++){
        if(buc[i]>mx) mx=buc[i],mxid=i;
    }
    if(mx<=(n+1)/2){
        priority_queue<pii> q;
        for(int i=0;i<26;i++) q.push(mk(buc[i],i));
        int la=-1;
        for(int i=1;i<=n;i++){
            pii tp=q.top();q.pop();
            if(tp.se==la){
                pii tmp=q.top();q.pop();
                q.push(tp);tp=tmp;
            }la=tp.se;
            cout<<(char)(tp.se+'a');
            tp.fi--;q.push(tp);
        }
    }else{
        int tp=0;
        for(int i=0;i<26;i++){
            if(i==mxid) continue;
            for(int j=1;j<=buc[i];j++)
                id[++tp]=i;
        }
        for(int i=0;i<=tp;i++) bf[i]=1,mx--;
        int x=0;
        while(mx>=2){
            bf[x]+=2,mx-=2;
            x++;if(x>tp) x=0;
        }if(mx) bf[tp]+=mx;
        for(int i=1;i<=bf[0];i++) cout<<(char)('a'+mxid);
        for(int i=1;i<=tp;i++){
            cout<<(char)('a'+id[i]);
            for(int j=1;j<=bf[i];j++) cout<<(char)('a'+mxid);
        }
    }cout<<endl;
}
int main(){
    //freopen("3.in","r",stdin);
    //freopen("3.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;cin>>t;
    while(t--) slv();
    cout.flush();
    cerr<<clock()*1.0/CLOCKS_PER_SEC<<endl;
    return 0;
}

Submission Info

Judge Result