Submission #6396589


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+5;
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) ret+=solve(i+1,p);
        return dp[i][j]=ret+1;
    }
    else return dp[i][j]=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

Submission Time
Task G - 辞書順
User meimon
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1524 Byte
Status WA
Exec Time 357 ms
Memory 251396 KB

Judge Result

Set Name All
Score / Max Score 0 / 4
Status
AC × 3
WA × 2
Set Name Test Cases
All 00, 01, 02, 90, 91
Case Name Status Exec Time Memory
00 WA 357 ms 251396 KB
01 WA 62 ms 204032 KB
02 AC 58 ms 203392 KB
90 AC 58 ms 203392 KB
91 AC 58 ms 203392 KB