Submission #22699

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
22699	2017-04-30T06:39:30 Z	past future present(#977, kazel, pjh0123, nemo)	Joyful KMP (KRIII5_JK)	C++14	0 / 7	26 ms	10880 KB

JK

#include<stdio.h>
#include<string.h>

using ll = long long;
const int mod = 1e9 + 7;
char s[1000005], ans[1000005];
int n, ff[1000005];


void calculate_pi() {
	ff[0] = -1;
	for (int i = 1, j = -1; i < n; i++) {
		while (j >= 0 && s[i] != s[j + 1]) j = ff[j];
		if (s[i] == s[j + 1])
			ff[i] = ++j;
		else
			ff[i] = -1;
	}
}

int pt[1000005], psz;

int main()
{
	ll k;
	scanf("%s%lld", s,&k);
	n = strlen(s);
	calculate_pi();
	int num = 26;
	for (int i = 1; i < n; i++)
		if (ff[i] == -1)
		{
			if (s[ff[i-1]+1] == s[0]){
				num = (num * 25LL) % mod;
			}
			else{
				num = (num * 24LL) % mod;
			}
			pt[++psz] = i;
		}
	printf("%d\n", num);
	k--;
	for (int j = psz; j >= 0; j--)
	{
		ans[pt[j]] = 'a' + k % 25;
		k /= 25;
	}
	if (k > 0)
	{
		puts("OVER");
		return 0;
	}
	for (int i = 1; i < n; i++)
	{
		if (ans[i])
		{
			if (ans[i] >= ans[0]) ans[i]++;
			continue;
		}
		ans[i] = ans[ff[i]];
	}
	puts(ans);
}

Compilation message

JK.cpp: In function 'int main()':
JK.cpp:26:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s%lld", s,&k);
                       ^

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	10880 KB	Output is correct
2	Correct	0 ms	10880 KB	Output is correct
3	Partially correct	0 ms	10880 KB	Output is partially correct
4	Partially correct	0 ms	10880 KB	Output is partially correct
5	Partially correct	19 ms	10880 KB	Output is partially correct
6	Partially correct	19 ms	10880 KB	Output is partially correct
7	Partially correct	23 ms	10880 KB	Output is partially correct
8	Partially correct	26 ms	10880 KB	Output is partially correct
9	Partially correct	23 ms	10880 KB	Output is partially correct
10	Correct	0 ms	10880 KB	Output is correct
11	Correct	0 ms	10880 KB	Output is correct
12	Incorrect	0 ms	10880 KB	Output isn't correct
13	Halted	0 ms	0 KB	-