/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 320.0 KiB
#2 Accepted 1ms 436.0 KiB
#3 Accepted 1ms 532.0 KiB
#4 Accepted 1ms 424.0 KiB
#5 Accepted 58ms 5.324 MiB
#6 Accepted 55ms 5.438 MiB
#7 Accepted 54ms 5.406 MiB
#8 Accepted 52ms 5.453 MiB
#9 Accepted 58ms 5.406 MiB
#10 Accepted 53ms 5.43 MiB
#11 Accepted 1ms 532.0 KiB
#12 Accepted 1ms 532.0 KiB
#13 Accepted 1ms 532.0 KiB
#14 Accepted 1ms 532.0 KiB
#15 Accepted 1ms 480.0 KiB
#16 Accepted 1ms 532.0 KiB
#17 Accepted 1ms 480.0 KiB
#18 Accepted 1ms 532.0 KiB
#19 Accepted 1ms 532.0 KiB
#20 Accepted 1ms 532.0 KiB
#21 Accepted 1ms 532.0 KiB
#22 Accepted 1ms 532.0 KiB
#23 Accepted 1ms 324.0 KiB
#24 Accepted 1ms 340.0 KiB
#25 Accepted 1ms 532.0 KiB
#26 Accepted 1ms 488.0 KiB
#27 Accepted 1ms 532.0 KiB
#28 Accepted 1ms 532.0 KiB
#29 Accepted 1ms 532.0 KiB
#30 Accepted 1ms 532.0 KiB
#31 Accepted 1ms 380.0 KiB
#32 Accepted 1ms 344.0 KiB
#33 Accepted 1ms 324.0 KiB
#34 Accepted 1ms 356.0 KiB
#35 Accepted 1ms 508.0 KiB
#36 Accepted 1ms 532.0 KiB
#37 Accepted 1ms 440.0 KiB
#38 Accepted 1ms 532.0 KiB
#39 Accepted 1ms 516.0 KiB
#40 Accepted 1ms 560.0 KiB
#41 Accepted 1ms 532.0 KiB
#42 Accepted 1ms 408.0 KiB
#43 Accepted 1ms 380.0 KiB
#44 Accepted 1ms 532.0 KiB
#45 Accepted 1ms 320.0 KiB
#46 Accepted 1ms 320.0 KiB
#47 Accepted 1ms 568.0 KiB
#48 Accepted 1ms 340.0 KiB
#49 Accepted 1ms 480.0 KiB
#50 Accepted 1ms 532.0 KiB
#51 Accepted 1ms 532.0 KiB
#52 Accepted 1ms 532.0 KiB
#53 Accepted 1ms 532.0 KiB
#54 Accepted 1ms 320.0 KiB
#55 Accepted 1ms 520.0 KiB
#56 Accepted 1ms 532.0 KiB
#57 Accepted 1ms 532.0 KiB
#58 Accepted 1ms 532.0 KiB
#59 Accepted 1ms 484.0 KiB
#60 Accepted 1ms 532.0 KiB
#61 Accepted 1ms 448.0 KiB
#62 Accepted 1ms 532.0 KiB
#63 Accepted 1ms 560.0 KiB
#64 Accepted 1ms 452.0 KiB
#65 Accepted 1ms 496.0 KiB
#66 Accepted 1ms 324.0 KiB
#67 Accepted 1ms 532.0 KiB
#68 Accepted 1ms 532.0 KiB
#69 Accepted 1ms 532.0 KiB
#70 Accepted 1ms 532.0 KiB
#71 Accepted 1ms 532.0 KiB
#72 Accepted 2ms 324.0 KiB
#73 Accepted 2ms 532.0 KiB
#74 Accepted 4ms 532.0 KiB
#75 Accepted 4ms 532.0 KiB
#76 Accepted 4ms 532.0 KiB
#77 Accepted 4ms 532.0 KiB
#78 Accepted 4ms 536.0 KiB
#79 Accepted 4ms 532.0 KiB
#80 Accepted 4ms 764.0 KiB
#81 Accepted 4ms 532.0 KiB
#82 Accepted 4ms 532.0 KiB
#83 Accepted 4ms 324.0 KiB
#84 Accepted 4ms 532.0 KiB
#85 Accepted 4ms 532.0 KiB
#86 Accepted 4ms 532.0 KiB
#87 Accepted 4ms 532.0 KiB
#88 Accepted 4ms 536.0 KiB
#89 Accepted 4ms 532.0 KiB
#90 Accepted 4ms 532.0 KiB
#91 Accepted 4ms 324.0 KiB
#92 Accepted 4ms 452.0 KiB
#93 Accepted 4ms 532.0 KiB
#94 Accepted 4ms 532.0 KiB
#95 Accepted 4ms 532.0 KiB
#96 Accepted 4ms 532.0 KiB
#97 Accepted 4ms 532.0 KiB
#98 Accepted 4ms 532.0 KiB
#99 Accepted 4ms 352.0 KiB
#100 Accepted 4ms 532.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});

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

    ll ache = 0;
    for (ll i = 0; i < n; ) {
        if (indx[i] == i) {
            cout << s[i];
            ache++;
            i++;
            continue;
        }

        if (i+k >= n) {
            if (ache + (n-i) >= k) {
                string temp = s.substr(i);
                sort(temp.begin(), temp.end());
                cout << temp;
            }  
            else cout << s.substr(i);
            break;
        }

        string temp = s.substr(i, k);
        sort(temp.begin(), temp.end());
        cout << temp;
        i += k;
        ache = 0;
    }
}

Information

Submit By
Type
Submission
Problem
P1230 Lexicographically Smallest Rearrangement
Language
C++17 (G++ 13.2.0)
Submit At
2025-09-05 16:43:50
Judged At
2025-09-05 16:43:50
Judged By
Score
100
Total Time
58ms
Peak Memory
5.453 MiB