Submission #22781

#	Time	Username	Problem	Language	Result	Execution time	Memory
22781		팀명을 한번 정하면 못바꿀까? (#40)	Joyful KMP (KRIII5_JK)	C++14	2 / 7	143 ms	84012 KiB

JK

#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]];
				continue;
			}
		}
	}
	return 0;
}

Compilation message (stderr)

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);
                         ^

• Subtask 1: 2 / 1