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