Submission #1243729


Source Code Expand

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
using namespace std;

long long M=1000000007;
long long INF=1000000000000000001;
int main(int argc, char const *argv[]) {
  string ss;cin>>ss;
  long long m;cin>>m;
  int n=ss.length();
  vector<int> s(n);
  for(int i=0;i<n;++i)s[i]=(int)ss[i] - (int)('a');
  vector<vector<int>> mem(n+1,vector<int>(30));
  vector<long long> dp(n+1);
  dp[n-1]=1;
  for(int i=0;i<30;++i)mem[n][i]=n;
  for(int i=0;i<30;++i)mem[n-1][i]=n;
  mem[n-1][s[n-1]]=n-1;
  for(int i=n-2;i>-1;--i){
    for(int j=0;j<30;++j)mem[i][j]=mem[i+1][j];
    mem[i][s[i]]=i;
    dp[i]=dp[i+1]+dp[i+1]-dp[mem[i+2][s[i+1]]];
    if(dp[i]>INF)dp[i]=INF;
    // cout<<dp[i]<<endl;
  }
  long long tmp=0;
  for(int i=0;i<30;++i){
    tmp+=dp[mem[0][i]];
    if(tmp>INF)tmp=INF;
  }
  if(tmp<m){
    cout<<"Eel"<<endl;
  }
  string res="";
  int t=0;
  while(m>0){
    int k=0;
    for(k=0;m>0;++k){
      m-=dp[mem[t][k]];
    }
    k--;
    res=res+ss[mem[t][k]];
    m+=dp[mem[t][k]];
    m--;
    // if(m==1)break;
    t=mem[t][k]+1;
    // cout<<res<<endl;
  }
  cout<<res<<endl;


  return 0;
}

Submission Info

Submission Time
Task G - 辞書順
User pillow97
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1317 Byte
Status WA
Exec Time 213 ms
Memory 161540 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 AC 213 ms 161540 KB
01 AC 4 ms 2304 KB
02 WA 1 ms 256 KB
90 WA 1 ms 256 KB
91 AC 1 ms 256 KB