/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 764.0 KiB
#2 Accepted 1ms 532.0 KiB
#3 Accepted 1ms 400.0 KiB
#4 Accepted 1ms 532.0 KiB
#5 Accepted 59ms 48.699 MiB
#6 Accepted 57ms 48.578 MiB
#7 Accepted 58ms 48.719 MiB
#8 Accepted 60ms 48.715 MiB
#9 Accepted 60ms 48.762 MiB
#10 Accepted 58ms 48.723 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 496.0 KiB
#16 Accepted 1ms 532.0 KiB
#17 Accepted 1ms 324.0 KiB
#18 Accepted 2ms 532.0 KiB
#19 Accepted 2ms 532.0 KiB
#20 Accepted 2ms 532.0 KiB
#21 Accepted 4ms 532.0 KiB
#22 Accepted 4ms 532.0 KiB
#23 Accepted 4ms 324.0 KiB
#24 Accepted 4ms 532.0 KiB
#25 Accepted 4ms 324.0 KiB
#26 Accepted 4ms 532.0 KiB
#27 Accepted 4ms 532.0 KiB
#28 Accepted 4ms 532.0 KiB
#29 Accepted 4ms 344.0 KiB
#30 Accepted 4ms 532.0 KiB
#31 Accepted 4ms 532.0 KiB
#32 Accepted 4ms 564.0 KiB
#33 Accepted 4ms 532.0 KiB
#34 Accepted 5ms 356.0 KiB
#35 Accepted 4ms 532.0 KiB
#36 Accepted 4ms 320.0 KiB
#37 Accepted 4ms 532.0 KiB
#38 Accepted 4ms 532.0 KiB
#39 Accepted 4ms 532.0 KiB
#40 Accepted 4ms 340.0 KiB
#41 Accepted 4ms 532.0 KiB
#42 Accepted 5ms 484.0 KiB
#43 Accepted 4ms 348.0 KiB
#44 Accepted 4ms 532.0 KiB
#45 Accepted 4ms 532.0 KiB
#46 Accepted 4ms 532.0 KiB
#47 Accepted 4ms 560.0 KiB
#48 Accepted 4ms 344.0 KiB
#49 Accepted 4ms 340.0 KiB
#50 Accepted 4ms 532.0 KiB
#51 Accepted 4ms 532.0 KiB
#52 Accepted 4ms 532.0 KiB
#53 Accepted 4ms 320.0 KiB
#54 Accepted 4ms 532.0 KiB
#55 Accepted 4ms 532.0 KiB
#56 Accepted 4ms 532.0 KiB
#57 Accepted 4ms 532.0 KiB
#58 Accepted 4ms 444.0 KiB
#59 Accepted 4ms 532.0 KiB
#60 Accepted 4ms 348.0 KiB
#61 Accepted 4ms 532.0 KiB
#62 Accepted 4ms 344.0 KiB
#63 Accepted 4ms 344.0 KiB
#64 Accepted 4ms 484.0 KiB
#65 Accepted 4ms 532.0 KiB
#66 Accepted 4ms 532.0 KiB
#67 Accepted 4ms 532.0 KiB
#68 Accepted 4ms 532.0 KiB
#69 Accepted 4ms 320.0 KiB
#70 Accepted 4ms 536.0 KiB
#71 Accepted 4ms 532.0 KiB
#72 Accepted 4ms 532.0 KiB
#73 Accepted 4ms 532.0 KiB
#74 Accepted 4ms 328.0 KiB
#75 Accepted 4ms 532.0 KiB
#76 Accepted 4ms 532.0 KiB
#77 Accepted 4ms 532.0 KiB
#78 Accepted 4ms 532.0 KiB
#79 Accepted 4ms 532.0 KiB
#80 Accepted 4ms 532.0 KiB
#81 Accepted 4ms 532.0 KiB
#82 Accepted 4ms 532.0 KiB
#83 Accepted 4ms 324.0 KiB
#84 Accepted 5ms 500.0 KiB
#85 Accepted 5ms 496.0 KiB
#86 Accepted 4ms 532.0 KiB
#87 Accepted 4ms 532.0 KiB
#88 Accepted 4ms 532.0 KiB
#89 Accepted 4ms 344.0 KiB
#90 Accepted 4ms 484.0 KiB
#91 Accepted 4ms 532.0 KiB
#92 Accepted 4ms 532.0 KiB
#93 Accepted 4ms 532.0 KiB
#94 Accepted 4ms 532.0 KiB
#95 Accepted 4ms 320.0 KiB
#96 Accepted 4ms 320.0 KiB
#97 Accepted 5ms 488.0 KiB
#98 Accepted 4ms 532.0 KiB
#99 Accepted 4ms 324.0 KiB
#100 Accepted 4ms 532.0 KiB

Code

/**
 *    author:   Binoy Barman
 *    created:  2025-08-31 11:27:38
**/

#include<bits/stdc++.h>
#ifdef LOCAL
#include "algo/debug.h"
#else
#define dbg(...) 42
#endif
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int inf = 2e9;

#define int long long
#define nl '\n'
#define all(v) v.begin(), v.end()
#define clg(x) (32 - __builtin_clz(x))
#define Testcase_Handler int tts, tc = 0; cin >> tts; hell: while(tc++ < tts)
#define uniq(v) sort(all(v)), v.resize(distance(v.begin(), unique(v.begin(), v.end())))
template<class T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> istream& operator>>(istream& in, vector<T>& a) {for(auto &x : a) in >> x; return in;};
template<typename T> ostream& operator<<(ostream& out, vector<T>& a) {bool first = true;for(auto &x : a) {if(!first) out << ' ';first = false;out << x;}return out;};

namespace Dark_Lord_Binoy {
inline void init() {
    ios::sync_with_stdio(false); 
    cin.tie(nullptr);

    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}
}

int32_t main() {
    Dark_Lord_Binoy::init();

    int n, k;
    cin >> n >> k;

    string s, ans = "";
    cin >> s;
    s = '#' + s;

    vector<vector<int>> f(n + 1, vector<int>(26, 0));
    for (int i = 1; i <= n; i++) {
        f[i][s[i] - 'a']++;
        for (int j = 0; j < 26; j++) {
            f[i][j] += f[i - 1][j];
        }
    }

    int last_index = 0;
    for (int i = 1; i <= n;) {
        int r = i + k - 1;
        int lim = min(r, n);
        int cur = s[i] - 'a';

        vector<int> nxt_k(26, 0);
        bool exists = false;

        for (int j = 0; j < 26; j++) {
            nxt_k[j] = f[lim][j] - f[i][j];

            if(j < cur && nxt_k[j] > 0) {
                exists = true;
            }
        }

        if(exists) {
            string tmp = "";
            if(r > n) {
                if(n - last_index >= k) {
                    for (int id = i; id <= n; id++) {
                        tmp += s[id];
                    }
                    sort(all(tmp));
                    ans += tmp;
                    i = r + 1;
                } 
                else {
                    for (int id = i; id <= n; id++) {
                        ans += s[id];
                    }
                    i = r + 1;
                }
            }
            else {
                for (int id = i; id <= r; id++) {
                    tmp += s[id];
                }
                sort(all(tmp));
                ans += tmp;
                i = r + 1;
            }
            last_index = r;
        } 
        else {
            ans += s[i];
            i++;
        }
    }

    cout << ans << nl;

    dbg(_Time_);
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1230 Lexicographically Smallest Rearrangement
Contest
Testing - Intra LU Programming contest 25
Language
C++17 (G++ 13.2.0)
Submit At
2025-08-31 09:18:26
Judged At
2025-08-31 09:18:26
Judged By
Score
100
Total Time
60ms
Peak Memory
48.762 MiB