Submission #1454878


Source Code Expand

#include <algorithm>
#include <bitset>
#include <cassert>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <sstream>
#include <stdio.h>
#include <string>
#include <vector>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define POW(n) ((n) * (n))
#define ALL(a) (a).begin(), (a).end()
#define dump(v) (cerr << #v << ": " << v << endl)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<unsigned long long> vull;

// ll n = to_T<ll>("114514")
template <class T> T to_T(const string &s) {
  istringstream is(s);
  T res;
  is >> res;
  return res;
}
template <class T> string to_s(const T &a) {
  ostringstream os;
  os << a;
  return os.str();
}

ll count(string S, string T, std::vector<char> v) {
  int C[30] = {}, C2[30] = {};
  ll ret = 0;

  REP(i, S.size()) {
    C[S[i] - 'a']++;
    C2[S[i] - 'a']++;
  }

  REP(i, T.size()) {
    ret += (S[i] != T[i]) ? 1 : 0;
    C[S[i] - 'a']--;
    C2[T[i] - 'a']--;
  }

  ll same = 0;
  REP(i, 30) {
    same += min(C[i], C2[i]);
    if (C[i] != C2[i]) {
      cerr << (char)(i + 'a') << " " << C[i] << " " << C2[i] << endl;
    }
  }

  ret += (S.size() - T.size()) - same;

  // dump(same);
  // dump(v.size());
  // dump(T);
  dump(ret);

  return ret;
}

void solve(long long N, long long K, string S) {
  std::vector<char> v;
  REP(i, N) v.push_back(S[i]);
  sort(ALL(v));

  string ans = "";

  REP(i, N) {
    REP(j, v.size()) {
      cerr << ans << "+" << v[j] << " " << count(S, ans + v[j], v) << endl;
      if (count(S, ans + v[j], v) <= K) {

        ans += v[j];
        v.erase(v.begin() + j);
        sort(ALL(v));
        break;
      }
    }
  }

  cout << ans << endl;
}

int main() {
  ios::sync_with_stdio(false);
  string S;
  long long K;
  long long N;
  cin >> N;
  cin >> K;
  cin >> S;
  solve(N, K, S);
  return 0;
}

Submission Info

Submission Time
Task C - 辞書式順序ふたたび
User nosnosnos
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2032 Byte
Status AC
Exec Time 115 ms
Memory 256 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 58
Set Name Test Cases
All hand_1_0.txt, hand_1_1.txt, hand_1_2.txt, hand_1_3.txt, hand_1_4.txt, hand_1_5.txt, hand_1_6.txt, hand_1_7.txt, hand_1_8.txt, hand_2_0.txt, hand_2_1.txt, hand_2_10.txt, hand_2_2.txt, hand_2_3.txt, hand_2_4.txt, hand_2_5.txt, hand_2_6.txt, hand_2_7.txt, hand_2_8.txt, hand_2_9.txt, hand_3_2.txt, hand_3_3.txt, hand_3_4.txt, hand_3_5.txt, hand_3_6.txt, hand_4_2.txt, hand_4_3.txt, hand_4_4.txt, hand_4_5.txt, hand_4_6.txt, random_1.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_2.txt, random_3.txt, random_4.txt, random_5.txt, random_6.txt, random_7.txt, random_8.txt, random_9.txt, sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, small_1.txt, small_2.txt, small_3.txt, small_4.txt, small_5.txt, small_6.txt, small_7.txt, small_8.txt, small_9.txt
Case Name Status Exec Time Memory
hand_1_0.txt AC 1 ms 256 KB
hand_1_1.txt AC 1 ms 256 KB
hand_1_2.txt AC 1 ms 256 KB
hand_1_3.txt AC 1 ms 256 KB
hand_1_4.txt AC 1 ms 256 KB
hand_1_5.txt AC 1 ms 256 KB
hand_1_6.txt AC 1 ms 256 KB
hand_1_7.txt AC 1 ms 256 KB
hand_1_8.txt AC 1 ms 256 KB
hand_2_0.txt AC 2 ms 256 KB
hand_2_1.txt AC 2 ms 256 KB
hand_2_10.txt AC 1 ms 256 KB
hand_2_2.txt AC 2 ms 256 KB
hand_2_3.txt AC 2 ms 256 KB
hand_2_4.txt AC 1 ms 256 KB
hand_2_5.txt AC 2 ms 256 KB
hand_2_6.txt AC 1 ms 256 KB
hand_2_7.txt AC 1 ms 256 KB
hand_2_8.txt AC 1 ms 256 KB
hand_2_9.txt AC 1 ms 256 KB
hand_3_2.txt AC 2 ms 256 KB
hand_3_3.txt AC 1 ms 256 KB
hand_3_4.txt AC 2 ms 256 KB
hand_3_5.txt AC 1 ms 256 KB
hand_3_6.txt AC 1 ms 256 KB
hand_4_2.txt AC 3 ms 256 KB
hand_4_3.txt AC 3 ms 256 KB
hand_4_4.txt AC 3 ms 256 KB
hand_4_5.txt AC 2 ms 256 KB
hand_4_6.txt AC 2 ms 256 KB
random_1.txt AC 5 ms 256 KB
random_10.txt AC 88 ms 256 KB
random_11.txt AC 62 ms 256 KB
random_12.txt AC 115 ms 256 KB
random_13.txt AC 72 ms 256 KB
random_14.txt AC 27 ms 256 KB
random_15.txt AC 9 ms 256 KB
random_2.txt AC 13 ms 256 KB
random_3.txt AC 15 ms 256 KB
random_4.txt AC 24 ms 256 KB
random_5.txt AC 6 ms 256 KB
random_6.txt AC 48 ms 256 KB
random_7.txt AC 41 ms 256 KB
random_8.txt AC 38 ms 256 KB
random_9.txt AC 76 ms 256 KB
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
sample_3.txt AC 1 ms 256 KB
sample_4.txt AC 1 ms 256 KB
small_1.txt AC 1 ms 256 KB
small_2.txt AC 1 ms 256 KB
small_3.txt AC 1 ms 256 KB
small_4.txt AC 1 ms 256 KB
small_5.txt AC 1 ms 256 KB
small_6.txt AC 1 ms 256 KB
small_7.txt AC 1 ms 256 KB
small_8.txt AC 1 ms 256 KB
small_9.txt AC 1 ms 256 KB