Submission #40728159

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN=1e4+10;
int n,k;
char s[MAXN],t[MAXN],res[MAXN],tmp[MAXN],mn;

void OK(){
	rep(i,1,n)cout<<mn;
	exit(0);
}

void upd(){
	rep(i,1,n){
		if(t[i] != res[i] && t[i] < res[i])return;
		if(t[i] != res[i] && t[i] > res[i])break;
	}

	rep(i,1,n)t[i]=res[i];
}

int calc(char* s,char* tmp,int x){
	rep(i,1,x)tmp[i]=s[n-x+i];
	rep(i,1,n-x)tmp[x+i]=s[n-i+1];

	int cnt=0;
	per(i,n,1)if(tmp[i] != mn)break;else cnt++;
	return cnt;
}

void solve(int x){
	int cnt=calc(s,res,x);

	if(cnt==0)return upd();
	if(k>=20 || 1ll*cnt*(1<<(k-1)) >= n)OK();

	if(k==1){
		return upd();
	}
	rep(i,1,k-2){
		calc(res,tmp,n-cnt);
		rep(j,1,n)res[j]=tmp[j];
		cnt<<=1;
	}
	calc(res,tmp,cnt);
	rep(j,1,n)res[j]=tmp[j];

	upd();
}

int main(){

	cin>>n>>k>>(s+1);
	rep(i,1,n)t[i]=s[i];

	mn=s[1];
	rep(i,2,n)mn=min(mn,s[i]);

	rep(i,0,n)solve(i);

	cout<<(t+1)<<endl;
    return 0;
}

Submission Info

Judge Result