/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 1ms 532.0 KiB
#3 Accepted 1ms 532.0 KiB
#4 Accepted 1ms 324.0 KiB
#5 Accepted 5ms 844.0 KiB
#6 Accepted 6ms 880.0 KiB
#7 Wrong Answer 8ms 968.0 KiB
#8 Accepted 8ms 972.0 KiB
#9 Accepted 8ms 928.0 KiB
#10 Wrong Answer 8ms 932.0 KiB

Code

/**
 *    author:   Binoy Barman
 *    created:  2025-08-29 11:00:07
**/

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

int32_t main() {
    ios::sync_with_stdio(false); 
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    vector<int> f(26, 0);
    int i = 0, j = 0;
    while(i < n) {
        int r = i + k - 1;
        if(r >= n) break; // not enough length for a k-window
        if(r == n - 1) {
            sort(s.begin() + i, s.begin() + r + 1);
            break;
        }

        // build frequency for substring [i .. r]
        while(j < r) {
            f[s[j] - 'a']++;
            j++;
        }
        f[s[j] - 'a']++;
        
        // check if there exists a smaller character than s[i]
        int cur = s[i] - 'a';
        bool exists = false;
        for (int id = 0; id < cur; id++) {
            exists |= (f[id] > 0);
        }

        if(exists) {
            // sorting this window is optimal
            sort(s.begin() + i, s.begin() + r + 1);
            while(i <= r) {
                f[s[i] - 'a']--;
                i++;
            }
        }
        else {
            f[cur]--;
            i++;
        }
    }
    cout << s << '\n';
    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-30 16:02:48
Judged At
2025-08-30 16:02:48
Judged By
Score
8
Total Time
8ms
Peak Memory
972.0 KiB