| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 22803 |
2017-04-30T07:34:39 Z |
팀명을 한번 정하면 못바꿀까?(#898, qja0950) |
Joyful KMP (KRIII5_JK) |
C++14 |
|
226 ms |
84012 KB |
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <functional>
#include <set>
#include <map>
#include <queue>
#include <tuple>
#include <string.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
typedef long long ll;
typedef pair<int, int> pi;
const int MAX_N = 1e6 + 100, MOD = 1e9 + 7;
char P[MAX_N]; int N, F[MAX_N];
int S[MAX_N];
char Ans[MAX_N];
vector<int> D[MAX_N];
ll Memo[MAX_N][2]; int Next[MAX_N];
int main() {
scanf("%s", P+1); N = strlen(P+1);
for(int i=1; i<=N; i++) S[i] = i;
for(int i=2, k=0;i<=N;i++) {
vector<int> list;
while(k && P[k+1] != P[i]) {
// printf("Diff %d %d\n", k+1, i);
list.push_back(k+1);
k = F[k];
}
if(P[k+1] == P[i]) {
// printf("Same %d %d\n", k+1, i);
S[i] = S[k+1];
k++;
} else {
// printf("Diff %d %d\n", k+1, i);
list.push_back(k+1);
}
F[i] = k;
for(int x : list)
D[S[i]].push_back(S[x]);
}
for(int i=1; i<=N; i++) {
// printf("%d(%c) : %d\n", i, P[i], F[i]);
sort(D[i].begin(), D[i].end()); D[i].erase(unique(D[i].begin(), D[i].end()), D[i].end());
// printf("S : %d\n", S[i]);
// for(int x : D[i]) printf("%d ", x); puts("");
}
int ans = 1, past = N+1;
Memo[N+1][0] = 0; Memo[N+1][1] = 1;
ll be[2] = {0, 1}, base = 1e15;
for(int i=N; i>=1; i--) {
if(S[i] != i) continue;
int cnt = 0;
for(int x : D[i]) if(x < i) cnt++;
ans = 1ll * ans * (26 - cnt) % MOD;
Next[i] = past; past = i;
be[1] *= (26 - cnt);
if(be[0] < base) be[0] *= (26 - cnt);
be[0] += be[1] / base; be[1] %= base;
Memo[i][0] = be[0], Memo[i][1] = be[1];
}
printf("%d\n", ans);
ll K; scanf("%lld", &K);
if(be[0] < K/base || (be[0] == K/base && be[1] < K%base)) puts("OVER");
else {
for(int i=1; i<=N; i++) {
if(S[i] != i) {
Ans[i] = Ans[S[i]];
}else{
int cnt = 1, nt = Next[i];
ll val[2] = {Memo[nt][0], Memo[nt][1]};
while(val[0] < K/base || (val[0] == K/base && val[1] < K%base)) {
K -= val[1];
K -= val[0] * base;
cnt++;
}
vector<bool> chk = vector<bool>(26, false);
for(int x : D[i]) if(x < i) chk[Ans[x] - 'a'] = true;
for(int l=0; l<26; l++) {
if(chk[l] == false) cnt--;
if(cnt == 0) {
Ans[i] = 'a'+l;
break;
}
}
}
}
printf("%s\n", Ans+1);
}
return 0;
}
Compilation message
JK.cpp: In function 'int main()':
JK.cpp:26:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", P+1); N = strlen(P+1);
^
JK.cpp:69:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
ll K; scanf("%lld", &K);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
53916 KB |
Output is correct |
| 2 |
Correct |
3 ms |
53916 KB |
Output is correct |
| 3 |
Correct |
3 ms |
53916 KB |
Output is correct |
| 4 |
Correct |
9 ms |
53916 KB |
Output is correct |
| 5 |
Correct |
189 ms |
83880 KB |
Output is correct |
| 6 |
Correct |
186 ms |
84012 KB |
Output is correct |
| 7 |
Correct |
213 ms |
84012 KB |
Output is correct |
| 8 |
Correct |
216 ms |
84012 KB |
Output is correct |
| 9 |
Correct |
226 ms |
83880 KB |
Output is correct |
| 10 |
Correct |
3 ms |
53916 KB |
Output is correct |
| 11 |
Correct |
9 ms |
53916 KB |
Output is correct |
| 12 |
Correct |
6 ms |
53916 KB |
Output is correct |
| 13 |
Correct |
6 ms |
54048 KB |
Output is correct |
| 14 |
Correct |
6 ms |
54048 KB |
Output is correct |
| 15 |
Correct |
9 ms |
54616 KB |
Output is correct |
| 16 |
Correct |
29 ms |
55236 KB |
Output is correct |
| 17 |
Correct |
83 ms |
60240 KB |
Output is correct |
| 18 |
Correct |
166 ms |
66752 KB |
Output is correct |
| 19 |
Correct |
166 ms |
67508 KB |
Output is correct |
| 20 |
Correct |
153 ms |
67252 KB |
Output is correct |
| 21 |
Correct |
153 ms |
66824 KB |
Output is correct |
| 22 |
Correct |
169 ms |
66892 KB |
Output is correct |
| 23 |
Correct |
26 ms |
53916 KB |
Output is correct |
| 24 |
Correct |
23 ms |
53916 KB |
Output is correct |
| 25 |
Correct |
23 ms |
53916 KB |
Output is correct |
| 26 |
Correct |
23 ms |
53916 KB |
Output is correct |
| 27 |
Correct |
16 ms |
53916 KB |
Output is correct |
| 28 |
Correct |
23 ms |
53916 KB |
Output is correct |
| 29 |
Correct |
16 ms |
53916 KB |
Output is correct |
| 30 |
Correct |
23 ms |
53916 KB |
Output is correct |
| 31 |
Correct |
43 ms |
53916 KB |
Output is correct |
| 32 |
Correct |
23 ms |
53916 KB |
Output is correct |
| 33 |
Correct |
13 ms |
53916 KB |
Output is correct |
| 34 |
Correct |
19 ms |
53916 KB |
Output is correct |
| 35 |
Correct |
23 ms |
53916 KB |
Output is correct |
| 36 |
Correct |
33 ms |
53916 KB |
Output is correct |
| 37 |
Correct |
36 ms |
53916 KB |
Output is correct |
| 38 |
Correct |
23 ms |
53916 KB |
Output is correct |
| 39 |
Correct |
26 ms |
53916 KB |
Output is correct |
| 40 |
Correct |
29 ms |
53916 KB |
Output is correct |
| 41 |
Correct |
13 ms |
53916 KB |
Output is correct |
| 42 |
Correct |
23 ms |
53916 KB |
Output is correct |
| 43 |
Correct |
23 ms |
53916 KB |
Output is correct |
| 44 |
Correct |
23 ms |
53916 KB |
Output is correct |
| 45 |
Correct |
23 ms |
53916 KB |
Output is correct |
| 46 |
Correct |
26 ms |
53916 KB |
Output is correct |
| 47 |
Correct |
16 ms |
53916 KB |
Output is correct |
| 48 |
Correct |
29 ms |
53916 KB |
Output is correct |
| 49 |
Correct |
19 ms |
53916 KB |
Output is correct |
| 50 |
Correct |
23 ms |
53916 KB |
Output is correct |
