Submission #22677

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
22677	2017-04-30T06:26:44 Z	크리님 제가 귀여우면 됬지 뭘 더 원하세요 진짜(#952, sys7961, hyorothy, skdudn321)	Joyful KMP (KRIII5_JK)	C++11	0 / 7	0 ms	3012 KB

JK

#include<bits/stdc++.h>
using std::vector;
std::set<char> set;
char str[1001000];
unsigned long long k;
unsigned long long c[30][30];
const long long MOD = 1000000007;
vector<char> ans;
bool chk[30];
int n;
vector<int> pi;

std::vector<int> preprocessing(std::string p) {
	int m = p.size();
	std::vector<int> pi(m);
	pi[0] = 0;
	int j = 0;
	for (int i = 1; i<m; i++) {
		while (j>0 && p[i] != p[j]) {
			j = pi[j - 1];
		}
		if (p[i] == p[j]) {
			pi[i] = j + 1;
			j += 1;
		}
		else {
			pi[i] = 0;
		}
	}
	return pi;
}
bool dfs(int idx,unsigned long long p) {
	if (idx == n) {
		return p==1;
	}
	int u = 25 - idx;
	int len = n - idx - 1;
	unsigned long long q = 1;
	for (int i = u; i > u-len; i--) {
		q *= i;
		if (q >= p) {
			if (!chk[0]) {
				chk[0] = true;
				if (dfs(idx + 1, p)) {
					ans.push_back('a');
					return true;
				}
				chk[0] = false;
				return false;
			}
			break;
		}
		
	}
	if (!chk[0]) {
		p -= q*c[u][len];
	}
	for (int i = 1; i < 26; i++) {
		if (!chk[i]) {
			chk[i] = true;
			if (q >= p) {
				if (dfs(idx + 1, p)) {
					ans.push_back('a' + i);
					return true;
				}
				return false;
			}
			p -= q;
			chk[i] = false;
		}
	}
	return false;

}
int main() {
	for (int i = 0; i < 30; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0 || j == i)c[i][j] = 1;
			else c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
		}
	}
	scanf("%s%llu", str, &k);
	pi = preprocessing(str);

	vector<char> order;
	for (int i = 0; str[i] != '\0'; i++) {
		if (set.count(str[i]) == 0) {
			set.insert(str[i]);
			order.push_back(str[i]);
		}
	}
	n = set.size();
	long long sum = 26;
	for (int i = 1; i < pi.size(); i++) {
		if (pi[i] == 0) {
			sum *= 25;
			sum %= MOD;
		}
	}

	printf("%lld\n", sum);
	if (dfs(0, k)) {
		std::reverse(ans.begin(), ans.end());
		std::map<char, char> dic;
		for (int i = 0; i < ans.size(); i++) {
			dic[order[i]] = ans[i];
		}
		for (int i = 0; str[i] != '\0'; i++) {
			str[i] = dic[str[i]];
		}
		printf("%s", str);
	}
	else {
		printf("OVER");
	}

}

Compilation message

JK.cpp: In function 'int main()':
JK.cpp:94:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < pi.size(); i++) {
                    ^
JK.cpp:105:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < ans.size(); i++) {
                     ^
JK.cpp:82:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s%llu", str, &k);
                          ^

Subtask #1

0.0 / 1.0

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