Submission #22589

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

JK

#include<bits/stdc++.h>
using std::vector;
std::set<char> set;
char str[1001000];
long long k;
unsigned long long c[30][30];
const long long MOD = 1000000007;
vector<char> ans;
bool chk[30];
int n;
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 = 1; i <= len; i++) {
		q *= i;
		if (q*c[u][len] >= 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*c[u][len] >= p) {
				if (dfs(idx + 1, p)) {
					ans.push_back('a' + i);
					return true;
				}
				return false;
			}
			p -= q*c[u][len];
			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%lld", str, &k);


	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 = c[26][n] % MOD;
	for (int i = 1; i <= n; i++) {
		sum *= i;
		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:83:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < ans.size(); i++) {
                     ^
JK.cpp:62:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s%lld", str, &k);
                          ^

Subtask #1

0.0 / 1.0

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