Submission #1655495

---

Source Code Expand

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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG true

typedef long long ll;
typedef pair<int, int> ii;

string s;
int k;


string checker(string ss, int kk){
  string ret = ss;
  int i = 0, j = 0;
  string fst, sec;
  while(ss[i] != 'a'){
    i++;
    if(i == ss.size()) break;
  }
  fst = ss.substr(0, i);
  while(ss[i+j] == 'a'){
    j++;
    if(i+j == ss.size()) break;
  }
  sec = ss.substr(i, j);
  if(sec.size() == 0 || fst.size() > kk || fst.size() > sec.size()) return ss;
  else if(fst.size() < sec.size()){
    k -= fst.size();
    rep(ii, fst.size()) fst[i] = 'a';
    return (fst + sec + checker(ss.substr(i+j), kk - fst.size()));
  }
  else{
    string thi = ss.substr(i+j);
    if(thi < ss) {
      k -= fst.size();
      return (sec + sec + checker(thi, kk - fst.size()));
    }

    string buff = checker(thi, kk - fst.size());
    if(buff == thi) return ss;
    k -= fst.size();
    return (sec + sec + buff);
  }

  return ret;
}


int main(){

  cin >> s >> k;

  int na_cnt = 0;
  rep(i, s.size()) if(s[i] != 'a') na_cnt++;
  if(na_cnt<= k){
    rep(i, s.size() - k) cout << 'a';
    cout << endl;
  }
  else{
    int i = 0;
    while(s[i] == 'a'){
      i++;
      if(i == s.size()) break;
    }
    s = checker(s.substr(i), k);
    rep(i, s.size()){
      if(s[i] == 'a') continue;
      if(s.substr(i+1) < s.substr(i)) {
        s[i] = 'a';
        k--;
        if(k <= 0) break;
      }
      else break;
    }
    rep(i, k) cout << 'a';
    cout << s << endl;

    /*
    string ans = checker(s, k);
    rep(i, k) cout << 'a';
    cout << ans << endl;
    if(DEBUG) cout << k <<endl;
    */
  }


	return 0;
}

Submission Info

Judge Result