Submission #637830

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
int n,t;
int sa[300010],rnk[300010],tmp[300010];
bool compare_sa(int i,int j){
	if(rnk[i]!=rnk[j])	return rnk[i]<rnk[j];
	int ri=i+t<=n?rnk[i+t]:-1;
	int rj=j+t<=n?rnk[j+t]:-1;
	return ri<rj;
}
int main(){
	string s;	cin>>s;
	int k;	cin>>k;
	n=s.size();
	int acnt=0;
	for(int i=0;i<n;i++){
		if(s[i]=='a')	acnt++;
	}
	if(acnt+k>=n){
		int left=n-k;
		for(int i=0;i<left;i++)	cout<<"a";
		cout<<endl;
		return 0;
	}
	for(int i=0;i<=n;i++){
		sa[i]=i;
		rnk[i]=i<n?(s[i]-'a'):-1;
	}
	for(t=1;t<=n;t*=2){
		sort(sa,sa+n+1,compare_sa);
		tmp[sa[0]]=0;
		for(int i=1;i<=n;i++){
			tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0);
		}
		for(int i=0;i<=n;i++)	rnk[i]=tmp[i];
	}
	int left=0,right=0,cnt=0;
	acnt=0;
	for(int i=0;i<n;i++){
		if(s[i]=='a'){
			left=right=i+1;
			acnt++;
		}
		else	cnt++;
		if(k<=cnt){
			right=i+1;
			break;
		}
	}
	int sml=left;
	for(int i=left;i<=right;i++){
		if(rnk[sml]>rnk[i])	sml=i;
	}
	for(int i=0;i<acnt+k;i++)	cout<<"a";
	cout<<s.substr(sml)<<endl;
	return 0;
}

Submission Info

Judge Result