Submission #94425

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
94425	2019-01-18T11:40:08 Z	choikiwon	Joyful KMP (KRIII5_JK)	C++17	0 / 7	15 ms	8260 KB

JK

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

typedef long long ll;

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

void getPi(string S, int *pi) {
    for(int i = 1, j = 0; i < S.size(); i++) {
        while(j && S[i] != S[j]) j = pi[j - 1];
        if(S[i] == S[j]) {
            pi[i] = ++j;
        }
    }
}

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

int po[MN];

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

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

    po[0] = 1;
    for(int i = 1; i < MN; i++) {
        po[i] = 1LL * po[i - 1] * 25 % mod;
    }

    cin >> S >> K;

    getPi(S, pi);

    init();

    for(int i = 0; i < S.size(); i++) {
        if(pi[i]) {
            mrg(pi[i] - 1, i);
        }
    }

    for(int i = 0; i < S.size(); i++) if(fa[i] == i) V.push_back(i);

    int ans = 1LL * 26 * po[ (int)V.size() - 1 ] % mod;
    cout << ans << endl;
    if(ans < K) {
        cout << "OVER";
        return 0;
    }

    for(int i = 0; i < V.size(); i++) {
        for(int j = 0; j < 26; j++) {
            if(i && j == sol[ V[0] ]) continue;
            if(K > po[ (int)V.size() - 1 - i ]) {
                K -= po[ (int)V.size() - 1 - i ];
                continue;
            }
            sol[ V[i] ] = j;
            break;
        }
    }

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

Compilation message

JK.cpp: In function 'void getPi(std::__cxx11::string, int*)':
JK.cpp:10:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1, j = 0; i < S.size(); i++) {
                           ~~^~~~~~~~~~
JK.cpp: In function 'int main()':
JK.cpp:54:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < S.size(); i++) {
                    ~~^~~~~~~~~~
JK.cpp:60:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < S.size(); i++) if(fa[i] == i) V.push_back(i);
                    ~~^~~~~~~~~~
JK.cpp:69:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < V.size(); i++) {
                    ~~^~~~~~~~~~
JK.cpp:81:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < S.size(); i++) {
                    ~~^~~~~~~~~~

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	8260 KB	Output is correct
2	Correct	14 ms	8184 KB	Output is correct
3	Incorrect	13 ms	8184 KB	Output isn't correct
4	Halted	0 ms	0 KB	-