Submission #94431

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
94431	2019-01-18T12:22:28 Z	choikiwon	Joyful KMP (KRIII5_JK)	C++17	2 / 7	332 ms	82768 KB

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

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.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	27768 KB	Output is correct
2	Correct	26 ms	27780 KB	Output is correct
3	Partially correct	26 ms	27768 KB	Output is partially correct
4	Partially correct	23 ms	27768 KB	Output is partially correct
5	Partially correct	331 ms	82724 KB	Output is partially correct
6	Partially correct	332 ms	82732 KB	Output is partially correct
7	Partially correct	323 ms	82636 KB	Output is partially correct
8	Partially correct	326 ms	82768 KB	Output is partially correct
9	Partially correct	326 ms	82740 KB	Output is partially correct
10	Correct	23 ms	27768 KB	Output is correct
11	Correct	22 ms	27772 KB	Output is correct
12	Partially correct	23 ms	27768 KB	Output is partially correct
13	Partially correct	24 ms	27896 KB	Output is partially correct
14	Partially correct	24 ms	28152 KB	Output is partially correct
15	Partially correct	33 ms	29560 KB	Output is partially correct
16	Partially correct	43 ms	31092 KB	Output is partially correct
17	Partially correct	119 ms	44524 KB	Output is partially correct
18	Partially correct	231 ms	62444 KB	Output is partially correct
19	Partially correct	240 ms	62000 KB	Output is partially correct
20	Partially correct	231 ms	60856 KB	Output is partially correct
21	Partially correct	230 ms	61796 KB	Output is partially correct
22	Partially correct	222 ms	58732 KB	Output is partially correct
23	Partially correct	96 ms	37760 KB	Output is partially correct
24	Partially correct	98 ms	37612 KB	Output is partially correct
25	Partially correct	104 ms	37628 KB	Output is partially correct
26	Partially correct	106 ms	37692 KB	Output is partially correct
27	Partially correct	103 ms	37632 KB	Output is partially correct
28	Partially correct	105 ms	37632 KB	Output is partially correct
29	Partially correct	106 ms	37664 KB	Output is partially correct
30	Partially correct	103 ms	37632 KB	Output is partially correct
31	Partially correct	100 ms	37632 KB	Output is partially correct
32	Partially correct	97 ms	37664 KB	Output is partially correct
33	Partially correct	100 ms	37760 KB	Output is partially correct
34	Partially correct	105 ms	37764 KB	Output is partially correct
35	Partially correct	98 ms	37756 KB	Output is partially correct
36	Partially correct	96 ms	37632 KB	Output is partially correct
37	Partially correct	98 ms	37632 KB	Output is partially correct
38	Partially correct	102 ms	37616 KB	Output is partially correct
39	Partially correct	97 ms	37696 KB	Output is partially correct
40	Partially correct	97 ms	37624 KB	Output is partially correct
41	Partially correct	100 ms	37728 KB	Output is partially correct
42	Partially correct	97 ms	37760 KB	Output is partially correct
43	Partially correct	96 ms	37728 KB	Output is partially correct
44	Correct	97 ms	37632 KB	Output is correct
45	Correct	95 ms	37632 KB	Output is correct
46	Correct	108 ms	37684 KB	Output is correct
47	Correct	104 ms	37884 KB	Output is correct
48	Correct	103 ms	37760 KB	Output is correct
49	Partially correct	103 ms	37680 KB	Output is partially correct
50	Correct	101 ms	37632 KB	Output is correct