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 |
|
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 |