/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Wrong Answer 1ms 536.0 KiB
#2 Accepted 1ms 532.0 KiB
#3 Accepted 1ms 532.0 KiB
#4 Wrong Answer 1ms 480.0 KiB

Code

// @rakibul-islam

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

using ll = long long;
const ll oo = 1e17;
const ll mod = 1e9 + 7;

struct node{
  int ch;
  node(){
    ch = 26;
  }
};
 
struct segPoint{
  vector<node> tr;
  vector<int> a;
  segPoint(int N) {
    tr.resize(4 * N);
    a.resize(N);
  }

  void merge(node &res, node &l, node &r) {
    res.ch = min(l.ch, r.ch);
  }

  void build (int u, int s, int e) {
    if (s == e) {
      tr[u].ch = a[s];
      return;
    }
    int v = u << 1, w = v | 1, m = (s + e) >> 1;
    build(v, s, m);
    build(w, m + 1, e);
    merge(tr[u], tr[v], tr[w]);
  }

  auto query(int l, int r, int u, int s, int e){
    if(e < l || s > r)return node();
    if(s >= l && e <= r){
      return tr[u];
    }
    int v = u << 1, w = v | 1, m = (s + e) >> 1;
    auto left = query(l, r, v, s, m);
    auto right = query(l, r, w, m + 1, e);
    auto ret = node();
    merge(ret, left, right);
    return ret;
  }
};

void solve() {
  int n, k; cin >> n >> k;
  vector<int> a(n);
  string s; cin >> s;
  segPoint seg(n);
  for (int i = 0; i < n; i++) {
    seg.a[i] = int(s[i] - 'a');
  }
  seg.build(1, 0, n - 1);
  for (int i = 0; i < n; i++) {
    int r = i + k - 1;
    if (i >= n) break;
    auto qr = seg.query(i, r, 1, 0, n - 1);
    if (qr.ch != seg.a[i]) {
      sort(seg.a.begin() + i, seg.a.begin()+r+1);
      i += k;
    }
  }
  for (int i = 0; i < n; i++) {
    cout << char(seg.a[i] + 'a');
  }
  cout << "\n";
} 

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t = 1;  //cin >> t;
  for (int test = 1; test <= t; test++) {
    solve();
  }
  return 0;
}

Information

Submit By
Type
Submission
Problem
P1230 Lexicographically Smallest Rearrangement
Contest
LUCC Presents Intra LU Junior Programming Contest - Replay
Language
C++17 (G++ 13.2.0)
Submit At
2025-09-02 17:40:51
Judged At
2025-09-02 17:40:51
Judged By
Score
2
Total Time
1ms
Peak Memory
536.0 KiB