Submission #1454151

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))

#define MOD 1000000007
#define INF 1000000000
#define MAX_N 105

int N, K;
string S;
vector< pair<char, int> > sorted;
vector<char> change_pool;

int main()
{
    cin >> N >> K >> S;
    REP(i, S.length()) {
        sorted.push_back(make_pair(S[i], i));
    }
    SORT(sorted);
    string ans = S;
    if(K <= 1) {
        cout << ans << endl;
        return 0;
    }
    int cur = 0;
    while(K >= 2 && cur < S.length()) {
        if(S[cur] != '?' && S[cur] != sorted[cur].first) {
            change_pool.push_back(S[cur]);
            change_pool.push_back(sorted[cur].first);
            //printf("cur %d S[cur] %c sorted[cur].second %d sorted[cur].first %c\n",
            //        cur, S[cur], sorted[cur].second, sorted[cur].first);
            S[cur] = '?';
            S[sorted[cur].second] = '?';
            K -= 2;
        }
        else if(S[cur] != '?' && S[cur] == sorted[cur].first) {
            change_pool.push_back(S[cur]);
            S[cur] = '?';
        }
        else if(S[cur] == '?') {
            bool isFind = false;
            REP(i, change_pool.size()) {
                if(change_pool[i] == sorted[cur].first) {
                    isFind = true;
                    break;
                }
            }
            if(!isFind) {
                S[sorted[cur].second] = '?';
                change_pool.push_back(sorted[cur].first);
                K -= 1;
            }
        }
        cur++;
    }
    //cout << S << endl;
    while(K > 0) {
        pair<int, int> cand = make_pair(-1, 255);
        REP(i, S.length()) {
            //printf("%c %d\n", S[i], S[i]);
            if(S[i] != '?' && (int)S[i] < cand.second && S[i] != sorted[i].first) {
                cand = make_pair(i, S[i]);
            }
        }
        if(cand.first != -1) {
            S[cand.first] = '?';
            change_pool.push_back(cand.second);
        }
        K--;
    }
    //cout << S << endl;
    SORT(change_pool);
    int index = 0;
    REP(i, S.length()) {
        if(S[i] == '?') {
            S[i] = change_pool[index];
            index++;
        }
    }
    ans = S;

    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result