Submission #22289

#	Time	Username	Problem	Language	Result	Execution time	Memory
22289		↓우리보다잘하는팀 (#40)	Joyful KMP (KRIII5_JK)	C++14	7 / 7	99 ms	17716 KiB

JK

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const long long INF = 91e17;

char a[1000001];
int f[1000001];
int c[1000001];
int v[26];
long long d[1000001];

int main() {
	long long m;
	int i, j, k, l, n, r;
	scanf("%s%lld", a, &m);
	n = strlen(a);
	f[i = 0] = j = -1;
	while (i < n) {
		if (j == -1) {
			for (k = 0; k < 26; k++) {
				if (!v[k]) c[i]++;
				v[k] = 0;
			}
			f[++i] = ++j;
		}
		else if (a[i] == a[j]) {
			for (k = 0; k < 26; k++) v[k] = 0;
			c[i] = 1;
			f[++i] = ++j;
		}
		else {
			v[a[j] - 97] = 1;
			j = f[j];
		}
	}
	d[n] = r = 1;
	for (i = n - 1; i >= 0; i--) {
		r = 1ll * r * c[i] % 1000000007;
		d[i] = 1. * d[i + 1] * c[i] > INF ? INF : d[i + 1] * c[i];
	}
	printf("%d\n", r);
	if (d[0] < m) {
		puts("OVER");
		return 0;
	}
	m--;
	j = -1;
	for (i = 0; i < n; i++) {
		for (k = 0; k < 26; k++) v[k] = 0;
		while (f[i + 1] != j + 1) {
			v[a[j] - 97] = 1;
			j = f[j];
		}
		if (j != -1) k = a[j] - 97;
		else {
			l = m / d[i + 1];
			m %= d[i + 1];
			for (k = 0; k < 26; k++) {
				if (!v[k]) {
					if (!l) break;
					l--;
				}
			}
		}
		putchar(a[i] = k + 97);
		j++;
	}
}

Compilation message (stderr)

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

• Subtask 1: 7 / 1