/ SeriousOJ /

Record Detail

Time Exceeded


  
# 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 484.0 KiB
#5 Time Exceeded ≥2104ms ≥47.965 MiB
#6 Time Exceeded ≥2102ms ≥48.191 MiB

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;
    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) {
            if(r > n) {
                if(n - last_index >= k) {
                    sort(s.begin() + i, s.begin() + n + 1);
                    i += k;
                }
            }
            else {
                sort(s.begin() + i, s.begin() + r + 1);
                i += k;
            }
            last_index = r;
        } 
        else {
            i++;
        }
    }

    cout << s.substr(1) << 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:08:45
Judged At
2025-08-31 09:08:45
Judged By
Score
4
Total Time
≥2104ms
Peak Memory
≥48.191 MiB