Submission #1595297

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;

int n, k;
string s;

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin >> n >> k >> s;
	string t = s;
	sort(ALL(t));
	int miss = 0;
	FOR(i, n) {
		bool ok = true;
		if (t[i] != s[i]) {
			int cs[26], ct[26], cnt = 1;
			MEM(cs, 0);
			MEM(ct, 0);
			for (int j = i+1; j < n; j++) {
				cs[s[j]-'a']++;
				ct[t[j]-'a']++;
			}
			FOR(j, 26) cnt += max(0, cs[j]-ct[j]);
			if (miss + cnt > k) ok = false;
			else {
				miss += cnt;
				for (int j = i+1; j < n; j++) {
					if (s[j] == t[i]) {
						swap(s[i], s[j]);
						break;
					}
				}
			}
		}
		if (!ok) {
			for (int j = i; j < n; j++) t[j] = s[j];
			break;
		}
	}
	cout << t << endl;
	return 0;
}

Submission Info

Judge Result