Submission #2497029


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  string s;
  cin >> s;
  int k;
  cin >> k;

  priority_queue<pair<char, int>> que;
  REP(i, k) que.push({'z'+1, INF});
  REP(i, s.size()) {
    que.push({s[i], i});
    // cout << que.top() << endl;
    que.pop();
  }
  // cout << v << endl;

  VI v;
  while(que.size()) {
    v.PB(que.top().second);
    que.pop();
  }

  // cout << v << endl;

  vector<string> vs;
  for(int i: v) {
    REP(j, k) {
      if(i+j < s.size()) vs.PB(s.substr(i, j+1));
    }
  }

  sort(ALL(vs));
  vs.erase(unique(ALL(vs)), vs.end());

  cout << vs[k-1] << endl;

  return 0;
}

Submission Info

Submission Time
Task C - K-th Substring
User ferin_tech
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1735 Byte
Status
Exec Time 1 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 0_000.txt, 0_001.txt, 0_002.txt
Subtask 0 / 200 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt
All 0 / 100 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 2_011.txt, 2_012.txt, 2_013.txt, 2_014.txt, 2_015.txt, 2_016.txt, 2_017.txt, 2_018.txt
Case Name Status Exec Time Memory
0_000.txt 1 ms 256 KB
0_001.txt 1 ms 256 KB
0_002.txt 1 ms 256 KB
1_003.txt 1 ms 256 KB
1_004.txt 1 ms 256 KB
1_005.txt 1 ms 256 KB
1_006.txt 1 ms 256 KB
1_007.txt 1 ms 256 KB
1_008.txt 1 ms 256 KB
1_009.txt 1 ms 256 KB
1_010.txt 1 ms 256 KB
2_011.txt 1 ms 256 KB
2_012.txt 1 ms 256 KB
2_013.txt 1 ms 256 KB
2_014.txt 1 ms 256 KB
2_015.txt 1 ms 256 KB
2_016.txt 1 ms 256 KB
2_017.txt 1 ms 256 KB
2_018.txt 1 ms 256 KB