Submission #94429

#	Time	Username	Problem	Language	Result	Execution time	Memory
94429		choikiwon	Joyful KMP (KRIII5_JK)	C++17	2 / 7	352 ms	79064 KiB

JK

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;
const int MN = 1000010;

string S;
ll K;
int pi[MN], sol[MN];
vector<int> V[MN], P, more, smul, X;

int main() {
    std::ios::sync_with_stdio(false);

    cin >> S >> K;

    X.push_back(0);
    P.push_back(26);
    more.push_back(0);
    for(int i = 1, j = 0; i < S.size(); i++) {
        vector<int> chk(26, 0);
        while(j && S[i] != S[j]) {
            if(!chk[ S[j] - 'a' ]) {
                chk[ S[j] - 'a' ] = 1;
                V[i].push_back(j);
            }
            j = pi[j - 1];
        }
        if(S[i] == S[j]) {
            pi[i] = ++j;
        }
        else {
            if(!chk[ S[0] - 'a' ]) {
                V[i].push_back(0);
            }
            if(26 - (int)V[i].size() > 1) {
                more.push_back(P.size());
            }
            P.push_back(26 - (int)V[i].size());
            X.push_back(i);
        }
    }

    smul.resize(more.size());
    for(int i = (int)more.size() - 1; i >= 0; i--) {
        smul[i] = P[ more[i] ];
        if(i != (int)more.size() - 1) {
            smul[i] = 1LL * smul[i] * smul[i + 1] % mod;
        }
    }

    cout << smul[0] << endl;

    int pos1 = 0;
    for(int i = 0; i < X.size(); i++) {
        while(pos1 < more.size() && more[pos1] <= i) pos1++;

        int pos2 = 0;
        for(int j = 0; j < 26; j++) {
            if(pos2 < V[ X[i] ].size() && V[ X[i] ][pos2] == j) {
                pos2++;
                continue;
            }

            ll tmp = 1;
            for(int k = pos1; k < more.size(); k++) {
                if((K + tmp - 1) / tmp <= P[ more[k] ]) {
                    tmp = K;
                    break;
                }
                tmp *= P[ more[k] ];
            }
            if(K > tmp) {
                K -= tmp;
                continue;
            }
            sol[ X[i] ] = j;
            break;
        }
    }

    if(K != 1) {
        cout << "OVER";
        return 0;
    }

    for(int i = 0; i < S.size(); i++) {
        if(pi[i]) sol[i] = sol[ pi[i] - 1 ];
        cout << (char)('a' + sol[i]);
    }
}

Compilation message (stderr)

JK.cpp: In function 'int main()':
JK.cpp:22:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1, j = 0; i < S.size(); i++) {
                           ~~^~~~~~~~~~
JK.cpp:57:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < X.size(); i++) {
                    ~~^~~~~~~~~~
JK.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(pos1 < more.size() && more[pos1] <= i) pos1++;
               ~~~~~^~~~~~~~~~~~~
JK.cpp:62:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(pos2 < V[ X[i] ].size() && V[ X[i] ][pos2] == j) {
                ~~~~~^~~~~~~~~~~~~~~~~~
JK.cpp:68:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k = pos1; k < more.size(); k++) {
                               ~~^~~~~~~~~~~~~
JK.cpp:89:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < S.size(); i++) {
                    ~~^~~~~~~~~~

• Subtask 1: 2 / 1