/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 1ms 536.0 KiB
#3 Accepted 1ms 484.0 KiB
#4 Wrong Answer 1ms 536.0 KiB
#5 Accepted 62ms 5.488 MiB
#6 Accepted 62ms 5.477 MiB
#7 Accepted 62ms 5.566 MiB
#8 Accepted 63ms 5.309 MiB
#9 Accepted 66ms 5.324 MiB
#10 Accepted 61ms 5.43 MiB
#11 Accepted 2ms 364.0 KiB
#12 Accepted 1ms 320.0 KiB
#13 Accepted 1ms 324.0 KiB
#14 Accepted 1ms 496.0 KiB
#15 Accepted 1ms 484.0 KiB
#16 Accepted 1ms 536.0 KiB
#17 Accepted 1ms 324.0 KiB
#18 Accepted 1ms 324.0 KiB
#19 Accepted 1ms 320.0 KiB
#20 Wrong Answer 1ms 508.0 KiB

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n, k; cin >> n >> k;
    string s; cin >> s;

    if (n == k) {
        sort(s.begin(), s.end());
        cout << s << "\n";
        return 0;
    }

    ll indx[n];
    for (ll i = 0; i < n; i++) indx[i] = i;

    ll j = n-1;
    set<pair<char, ll>> st;
    for (ll i = n-1; i >= 0; i--) {
        if (st.size() >= k) {
            st.erase({s[j], j});
            j--;
        }
        st.insert({s[i], i});

        if (st.size() == k) {
            auto it = *st.begin();
            if (it.first < s[i]) indx[i] = it.second;
        }   
    }

    // for (auto &u : indx) cout << u << " "; cout << endl;

    for (ll i = 0; i < n; ) {
        if (indx[i] == i) {
            cout << s[i];
            i++;
            continue;
        }
        string temp;
        if (i+k >= n) temp = s.substr(i);
        else temp = s.substr(i, k);
        sort(temp.begin(), temp.end());
        cout << temp;
        i += k;
    }
}

Information

Submit By
Type
Submission
Problem
P1230 Lexicographically Smallest Rearrangement
Language
C++17 (G++ 13.2.0)
Submit At
2025-09-04 08:28:53
Judged At
2025-09-04 22:38:55
Judged By
Score
18
Total Time
66ms
Peak Memory
5.566 MiB