Submission #2113665


Source Code Expand

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vvi = vector<vi>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 102;

int main(){
  using vl = vector<ll>;
  using vvl = vector<vl>;
  int N; ll K; string s; cin >> s >> K;
  N = s.size();
  vvl dp(N+1,vl(26,0));
  vvi next(N+1,vi(26,N));
  rrep(i,N-1){
    next[i] = next[i+1];
    next[i][int(s[i]-'a')] = i;
  }
  rrep(i,N-1){
    rep(j,26){
      if(j==int(s[i]-'a')){
        rep(k,26) dp[i][j] += dp[i+1][k];
        dp[i][j] = min(dp[i][j]+1,K+1);
      }else{
        dp[i][j] = dp[i+1][j];
      }
    }
  }
  // rep(i,N){
  //   rep(j,26) printf("%3lld ",dp[i][j]);
  //   cout << "" << endl;
  // }
  string ans = "";
  int i = 0;
  while(true){
    // cout << i << " " << ans << endl ;
    if(K<=0){
      cout << ans << endl;
      return 0;
    }
    bool update = false;
    rep(j,26){
      if(K<=dp[i][j]){
        ans += char('a'+j);
        i = next[i][j]+1;
        K--;
        update = true;
        break;
      }else{
        K -= dp[i][j];
      }
    }
    if(update) continue;
    if(K>=0){
      cout << "Eel" << endl;
      return 0;
    }
  }
  return 0;
}

Submission Info

Submission Time
Task G - 辞書順
User kurarrr
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1617 Byte
Status WA
Exec Time 409 ms
Memory 376324 KB

Judge Result

Set Name All
Score / Max Score 0 / 4
Status
AC × 3
WA × 1
MLE × 1
Set Name Test Cases
All 00, 01, 02, 90, 91
Case Name Status Exec Time Memory
00 MLE 409 ms 376324 KB
01 WA 6 ms 4864 KB
02 AC 1 ms 256 KB
90 AC 1 ms 256 KB
91 AC 1 ms 256 KB