Submission #62131491

---

Source Code Expand

/*https://atcoder.jp/contests/arc191/tasks/arc191_a*/
/*2025年01月26日 21時09分06秒*/
// #include <atcoder/all>
// using namespace atcoder;
// using mint = modint998244353;
// using mint = modint1000000007;
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i, n) for (long long int i = 0; i < (n); ++i)
#define rep2(i, k, n) for (long long int i = (k); i < (n); ++i)
using namespace std;
using ll = long long;
using vint = vector<int>;
using vll = vector<ll>;
using vvint = vector<vector<int>>;
using vvll = vector<vector<ll>>;

// const ll INF = (ll)2e18+9;
const int INF = (int)2e9 + 7;

template <typename T>
void chmin(T& a, T b) {
    a = min(a, b);
}
template <typename T>
void chmax(T& a, T b) {
    a = max(a, b);
}

template <typename T>
void print(vector<T> v) {
    int n = v.size();
    rep(i, n) {
        if (i == 0)
            cout << v[i];
        else
            cout << ' ' << v[i];
    }
    cout << endl;
}

void yesno(bool x) {
    puts(x ? "Yes" : "No");
}

void solve();

int main() {
    solve();
    return 0;
}

void solve() {
    int N, M;
    cin >> N >> M;
    string S, T;
    cin >> S >> T;

    vector<pair<char, int>> t;
    rep(i, M) t.push_back({T[i], i});
    sort(rall(t));

    // for (auto [c, i] : t)
    //     cout << c << ' ' << i << endl;

    set<int> used;
    int i = 0, j = 0;
    while (i < N && j < M) {
        if (S[i] < t[j].first) {
            S[i] = t[j].first;
            used.insert(t[j].second);
            i++;
            j++;
        } else {
            i++;
        }
    }
    // cout << i << ' ' << j << endl;
    if (j < M) {
        rep2(k, j, M) {
            auto it = used.lower_bound(t[k].second);
            if (it != used.end()) {
                continue;
            }
            S[N - 1] = t[k].first;
            used.insert(t[k].second);
        }
    }
    cout << S << endl;
}

Submission Info

Judge Result