Submission #6396743

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;
 
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
const int mod=1e9+7;

string s,ans;
ll k;

const int max_s=1e6+7;
const ll INFDP=1e18+1;
ll dp[max_s][26];

void init(){
    rep(i,max_s) rep(j,26) dp[i][j]=-1;
    rep(i,26)dp[(int)s.size()][i]=0;
}

ll solve(int i,int j){
    if(i==(int)s.size())return 0;
    if(dp[i][j]!=-1)return dp[i][j];
    ll ret=0;
    if((int)s[i]-'a'==j){
        rep(p,26){
            ll tmp=solve(i+1,p);
            if(tmp+ret>1e18){
                ret=INFDP;break;
            }
            ret+=tmp;
        }
        return dp[i][j]=min(INFDP,ret+1);
    }
    else return dp[i][j]=min(INFDP,solve(i+1,j));
}

void getans(ll k,int x){
    if(k==0)return;
    if(k==1){
        ans+=s[x];return;
    }
    int p=x;
    rep(i,26){
        if(k-dp[x][i]<=0){
            while(i!=(int)s[p]-'a')++p;
            break;
        }
        else k-=dp[x][i];
        if(i==25){
            cout<<"Eel"<<endl;
            exit(0);
        }
    }
    ans+=s[p];
    getans(k-1,p+1);
    return;
}


int main(){
    cin>>s>>k;
    init();
    rep(i,26)solve(0,i);
    getans(k,0);
    cout<<ans<<endl;
}

Submission Info

Judge Result