Submission #1084142

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1084142	2024-09-05T10:57:52 Z	ksi4495	Joyful KMP (KRIII5_JK)	C++17	0 / 7	0 ms	348 KB

JK

//#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
//using namespace atcoder; //https://github.com/atcoder/ac-library

#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define bit(n, k) ((n >> k) & 1)
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef pair<int, int> pii;

const int mod=1e9+7;

map<int,char> mp;
set<char> st;
ll sum[27];
void solve(int cnt, ll k, int x=1, ll mul=26){
    if(x>cnt)return;
    if(x==cnt){
        assert(k<=mul);
        rep(i,0,k-1)st.erase(*st.begin());
        mp[x]=*st.begin();
        return;
    }
    if(cnt-x>=15){
        mp[x]=*st.begin();
        st.erase(st.begin());
        solve(cnt,k,x+1,mul-1);
        return;
    }
    ll A=1;
    for(ll i=1, j=mul-1; i<=cnt-x; i++,j--)A=A*j;
    int idx=0;
    while(k>A){
        idx++;
        k-=A;
    }
    vector<char> v;
    rep(i,0,idx){
        v.push_back(*st.begin());
        st.erase(st.begin());
    }
    mp[x]=*st.begin();
    st.erase(st.begin());
    for(char c:v)st.insert(c);
    solve(cnt,k,x+1,mul-1);
}

void test_case(int tt){
    string s; cin>>s;
    int n=(int)s.length();
    ll k; cin>>k;
    vector<int> a(26,0);
    int cnt=0;
    for(char &c:s){
        if(!a[c-'a']){
            a[c-'a']=++cnt;
        }
    }
    sum[0]=1;
    for(ll i=26, j=1; j<=cnt; j++,i--){
        if(j<=14)
            sum[j]=(sum[j-1]*i);
        else
            sum[j]=((sum[j-1]%mod)*i)%mod;
    }
    cout<<sum[cnt]%mod<<'\n';
    if(cnt<15 && k>sum[cnt]){
        cout<<"OVER\n";
        return;
    }
    for(char i='a'; i<='z'; i++)st.insert(i);
    solve(cnt,k);
    for(char &c:s){
        cout<<mp[a[c-'a']];
    }
    cout<<'\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    //cin>>t;
    rep(i, 1, t + 1)
    {
        test_case(i);
    }
    return 0;
}

Compilation message

JK.cpp: In function 'void test_case(int)':
JK.cpp:51:9: warning: unused variable 'n' [-Wunused-variable]
   51 |     int n=(int)s.length();
      |         ^

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Incorrect	0 ms	348 KB	Output isn't correct
3	Halted	0 ms	0 KB	-