답안 #22323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
22323	2017-04-30T03:54:17 Z	AcornCkiGs14004Team(#953, gs14004, cki86201, dotorya)	Joyful KMP (KRIII5_JK)	C++	컴파일 오류	0 ms	0 KB

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

JK.cpp: In function 'int main()':
JK.cpp:55:6: warning: 'auto' changes meaning in C++11; please remove it [-Wc++0x-compat]
  for(auto &i : v){
      ^
JK.cpp:55:12: error: ISO C++ forbids declaration of 'i' with no type [-fpermissive]
  for(auto &i : v){
            ^
JK.cpp:55:16: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
  for(auto &i : v){
                ^
JK.cpp:56:5: error: request for member 'first' in 'i', which is of non-class type 'int'
   i.first = disj.find(i.first);
     ^
JK.cpp:56:25: error: request for member 'first' in 'i', which is of non-class type 'int'
   i.first = disj.find(i.first);
                         ^
JK.cpp:57:5: error: request for member 'second' in 'i', which is of non-class type 'int'
   i.second = disj.find(i.second);
     ^
JK.cpp:57:26: error: request for member 'second' in 'i', which is of non-class type 'int'
   i.second = disj.find(i.second);
                          ^
JK.cpp:58:8: error: request for member 'first' in 'i', which is of non-class type 'int'
   if(i.first > i.second) swap(i.first, i.second);
        ^
JK.cpp:58:18: error: request for member 'second' in 'i', which is of non-class type 'int'
   if(i.first > i.second) swap(i.first, i.second);
                  ^
JK.cpp:58:33: error: request for member 'first' in 'i', which is of non-class type 'int'
   if(i.first > i.second) swap(i.first, i.second);
                                 ^
JK.cpp:58:42: error: request for member 'second' in 'i', which is of non-class type 'int'
   if(i.first > i.second) swap(i.first, i.second);
                                          ^
JK.cpp:62:6: warning: 'auto' changes meaning in C++11; please remove it [-Wc++0x-compat]
  for(auto &i : v){
      ^
JK.cpp:62:12: error: ISO C++ forbids declaration of 'i' with no type [-fpermissive]
  for(auto &i : v){
            ^
JK.cpp:62:16: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
  for(auto &i : v){
                ^
JK.cpp:63:9: error: request for member 'second' in 'i', which is of non-class type 'int'
   deg[i.second]++;
         ^
JK.cpp:64:9: error: request for member 'second' in 'i', which is of non-class type 'int'
   gph[i.second].push_back(i.first);
         ^
JK.cpp:64:29: error: request for member 'first' in 'i', which is of non-class type 'int'
   gph[i.second].push_back(i.first);
                             ^
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:96:9: warning: 'auto' changes meaning in C++11; please remove it [-Wc++0x-compat]
     for(auto &j : gph[i]){
         ^
JK.cpp:96:15: error: ISO C++ forbids declaration of 'j' with no type [-fpermissive]
     for(auto &j : gph[i]){
               ^
JK.cpp:96:19: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
     for(auto &j : gph[i]){
                   ^
JK.cpp:99:10: warning: unused variable 'prvx' [-Wunused-variable]
     lint prvx = x;
          ^