Submission #343493

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<vector>
using namespace std;
#define rep(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define rev(i,a,b) for(auto (i)=(b)-1;(i)>=(a);(i)--)

char id[101]; //K==Nの時の解
char ans[101];//解
char str[101];//元の文字列
char tmp[101];
char tp[101];
int N;//文字数
int K;//変えていい回数
int check(char *s1, char *s2){
	int r = 0;
	while (*s1 != '\0')
	if (*(s1++) != *(s2)++)r++;
	return r;
}



void cp(char *s, char *t){ rep(i, 0, N)t[i] = s[i]; }
void swaps(char *s, char *t){ auto u = (*s); (*s) = (*t); (*t) = u; }

void form(){
	int h = 0;
	rep(i, 0, N)if (ans[i] != str[i])tmp[h++] = ans[i];
	sort(tmp, tmp + h);
	h = 0;
	rep(i, 0, N)if (ans[i] != str[i])ans[i] = tmp[h++];
}

void solve(){
	int k = K;
	int n, m;
	while (k >= 2){
		if (check(id, ans) == 0)return;
		n = 0;
		while (id[n] == ans[n])n++;
		m = N-1;
		while ((m>n)&&!(id[n]==ans[m]&&str[m]!=ans[m]))m--;
		if (m == n){
			m = N - 1;
			while (id[n] != ans[m])m--;
		}
		swaps(ans + n, ans + m);
		form();
		k = K - check(str, ans);
		//cout << ans << k << endl;
	}
	
	if (k == 1){
		cp(ans, id);
		cp(ans, tp);
		rep(i, 0, N)
			rep(j, 0, N){
				swaps(ans + i, ans + j);
				form();
				if (check(str, ans) <= K)
				if (strcmp(ans, id) < 0)
					cp(ans, id);
				cp(tp, ans);
			}
		cp(id, ans);
	}
	
}


int main(void){
	
	cin>> N >> K;
	cin >> str;
	cp(str, ans);
	cp(str, id);
	sort(id, id + N);

	solve();
	cout << ans << endl; 

}

Submission Info

Judge Result