/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Wrong Answer 1ms 648.0 KiB
#3 Wrong Answer 1ms 532.0 KiB

Code

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

//using u128 = __uint128_t;
#define int                 long long

#define endl                "\n"
#define yes                 cout<<"YES\n"
#define no                  cout<<"NO\n"
#define nl                  cout<<"\n"
#define cnl                 clog<<"\n"

#define lin(n)              int n;cin>>n;
#define vin                 vector<int>
#define pr                  pair<int, int>
#define pp                  pop_back()
#define pb                  push_back
#define em_pb               emplace_back
#define all(x)              x.begin(),x.end()
#define ppfr(v)             v.erase(v.begin());
#define sum_all(v)          accumulate(all(v), 0ll)

#define forn(i,n)           for(int i = 0; i < n; i++)
#define Forn(i,n)           for(int i = 1; i <= n; i++)
#define rforn(i,n)          for(int i = n - 1; i >= 0; i--)
#define print(arr)          for(auto x: arr)cout<<x<<" ";nl;
#define mprint(mp)          for(auto a : mp)cout<<a.first<<" "<<a.second<<endl;

#define _log2(n)            31 - __builtin_clz(n)
#define pop_count(n)        __builtin_popcount(n)

mt19937                     rng(chrono::steady_clock::now().time_since_epoch().count());
#define rng(x,y)            uniform_int_distribution<int>(x,y)(rng)

#ifdef DEBUG
#include<algo/debug.h>
#else
#   define clog if (0) cerr
#   define NB 2500
#   define db(...) "" 
#endif

// const int M = 998244353;
const long long INF = 1e18;
const int M = 1e9 + 7;
const int N = 2e5 + 100;

int pf[150][N];

void _(){
  int n, k;
  cin >> n >> k;
  string str;
  cin >> str;
  str = "*" + str;

  for(int i = 1; i <= n; i++){
    pf[str[i]][i]++;
    for(int j = 'a'; j <= 'z'; j++){
      pf[j][i] += pf[j][i - 1];
    }
  }

  auto range = [&](int l, int r){
    vin v(150);
    for(int i = 'a'; i <= 'z'; i++){
      v[i] = pf[i][r] - pf[i][l - 1];
    }
    return v;
  };



  for(int i = 1, cnt = 0; i <= n - k + 1; i++){
    vin q = range(i, i + k - 1);
    int r = i + k - 1;
    int l = i;

    for(int c = 'a'; c <= 'z'; c++){
      if(!q[c])continue;
      cnt = q[c];
      while(i <= r and cnt and str[i] == c){
        i++; cnt--;
      }
      if(cnt)break;
    }
    // clog << i <<" "<< cnt << endl;
    if((i + k) > n and i < n){
      sort(str.begin() + i, str.end());
      break;
    }
    if(cnt){
      sort(str.begin() + i, str.begin() + i + k);
      i += k - 1;
    }
  }
  ppfr(str);
  cout << str << endl;
      
    
}

int32_t main(){
    
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);

  int test = 1;  
  // cin>>test;
  for(int i = 1; i <= test; i++){
      // cout << "Case " << i <<": ";
      _();
  }
  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:05:24
Judged At
2025-09-02 17:05:24
Judged By
Score
1
Total Time
1ms
Peak Memory
648.0 KiB