Submission #94431

#	Time	Username	Problem	Language	Result	Execution time	Memory
94431		choikiwon	Joyful KMP (KRIII5_JK)	C++17	2 / 7	332 ms	82768 KiB

JK

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

typedef long long ll;

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

int fa[MN];
void init() {
    for(int i = 0; i < MN; i++) fa[i] = i;
}
int find(int u) {
    if(fa[u] == u) return u;
    else return fa[u] = find(fa[u]);
}
void mrg(int u, int v) {
    u = find(u);
    v = find(v);
    if(u == v) return;
    fa[v] = u;
}

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;

    init();
    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;
            mrg(pi[i] - 1, i);
        }
        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() && sol[ find(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:38:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1, j = 0; i < S.size(); i++) {
                           ~~^~~~~~~~~~
JK.cpp:74:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < X.size(); i++) {
                    ~~^~~~~~~~~~
JK.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(pos1 < more.size() && more[pos1] <= i) pos1++;
               ~~~~~^~~~~~~~~~~~~
JK.cpp:79:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(pos2 < V[ X[i] ].size() && sol[ find(V[ X[i] ][pos2]) ] == j) {
                ~~~~~^~~~~~~~~~~~~~~~~~
JK.cpp:85:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k = pos1; k < more.size(); k++) {
                               ~~^~~~~~~~~~~~~
JK.cpp:106:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < S.size(); i++) {
                    ~~^~~~~~~~~~

• Subtask 1: 2 / 1