Submission #1455142

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>

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;   // ソート済みの S, ソート前の位置
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;
    }
    else if (N <= K) {
        REP(i, sorted.size()) {
            printf("%c", sorted[i].first);
        }
        printf("\n");
        return 0;
    }
    int sorted_ind_begin = 0;
    REP(cur, S.length()) {
        for (int i = 0; i < sorted.size(); ++i) {
            if (S[cur] != '?' && sorted[i].first != '*' && S[cur] != sorted[i].first) {
                int change_cost = 2;
                if (S[sorted[i].second] == '?') { change_cost = 1; }
                if (K - change_cost >= 0) {
                    // 変更可能
                    if (change_cost == 2) {
                        change_pool.push_back(S[cur]);
                        change_pool.push_back(sorted[i].first);
                        S[cur] = '?';
                        S[sorted[i].second] = '?';
                        sorted[i].first = '*';
                    }
                    if (change_cost == 1) {
                        change_pool.push_back(S[cur]);
                        S[cur] = '?';
                        sorted[i].first = '*';
                    }
                    K -= change_cost;
                    break;
                }

            }
            else if (S[cur] == sorted[i].first) {
                sorted[i].first = '*';
                break;
            }
        }
        if (K == 0) { break; }
    }
    SORT(change_pool);
    int pool_ind = 0;
    REP(i, S.length()) {
        if (S[i] == '?') {
            S[i] = change_pool[pool_ind];
            pool_ind++;
        }
    }
    cout << S << endl;
    return 0;
}

Submission Info

Judge Result