Submission #22948

#	Time	Username	Problem	Language	Result	Execution time	Memory
22948		gs14004	Joyful KMP (KRIII5_JK)	C++11	7 / 7	366 ms	85180 KiB

JK

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef unsigned long long kriii;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
 
struct disj{
	int pa[1000005];
	void init(int n){
		for(int i=0; i<=n; i++) pa[i] = i;
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[q] = p; return 1;
	}
}disj;
 
vector<int> gph[1000005];
vector<pi> v;
char str[1000005];
char rchr[1000005];
int fail[1000005];
kriii cnt[1000005];
lint k;
 
int n, deg[1000005];
 
int main(){
	cin >> str >> k;
	n = strlen(str);
	disj.init(n);
	int p = 0;
	for(int i=1; str[i]; i++){
		while(p > 0 && str[i] != str[p]){
			v.push_back(pi(p, i));
			p = fail[p];
		}
		if(str[i] == str[p]){
		//	printf("uni %d %d\n", i, p);
			disj.uni(p, i);
			p++;
		}
		else{
			v.push_back(pi(p, i));
		}
		fail[i+1] = p;
	}
	for(auto &i : v){
		i.first = disj.find(i.first);
		i.second = disj.find(i.second);
		if(i.first > i.second) swap(i.first, i.second);
	}
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	for(auto &i : v){
		deg[i.second]++;
		gph[i.second].push_back(i.first);
	}
	lint ans = 1;
	for(int i=0; i<n; i++){
		if(disj.find(i) == i){
			ans *= max(0, 26 - deg[i]);
			ans %= mod;
		}
	}
	cout << ans << endl;
	kriii tmp = 1;
	for(int i=n-1; i>=0; i--){
		if(disj.find(i) == i){
			cnt[i] = tmp;
			tmp = 0;
			for(int j=0; j<26-deg[i]; j++){
				tmp += cnt[i];
				if(tmp > k) tmp = k+1;
			}
		}
	}
	if(tmp < k){
		cout << "OVER";
		return 0;
	}
	else{
		k--;
		for(int i=0; i<n; i++){
			if(disj.find(i) == i){
				lint x = k / cnt[i];
				k -= x * cnt[i];
				int mark[26] = {};
				for(auto &j : gph[i]){
					mark[rchr[j] - 'a'] = 1;
				}
				lint prvx = x;
				for(int j=0; j<26; j++){
					if(!mark[j]) x--;
					if(x == -1){
						rchr[i] = j + 'a';
						break;
					}
				}
			}
		}
		for(int i=0; i<n; i++) putchar(rchr[disj.find(i)]);
	}
}

Compilation message (stderr)

JK.cpp: In function 'int main()':
JK.cpp:81:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(tmp > k) tmp = k+1;
            ^
JK.cpp:85:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(tmp < k){
         ^
JK.cpp:99:10: warning: unused variable 'prvx' [-Wunused-variable]
     lint prvx = x;
          ^

• Subtask 1: 7 / 1