fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. using ll=long long int;
  4. using llu=long long unsigned int;
  5. const int N=1e6+5;
  6.  
  7. //int x;
  8. int g[N][26];
  9. queue<int> q;
  10. int states=1;
  11. int f[N];
  12. int isEnd[N];
  13. string str;
  14. string s;
  15. llu dp[2500][35][2][2][2];
  16. int visited[2500][35][2][2][2];
  17. int n;
  18.  
  19. int nextstate(int &state,int ch){
  20.  
  21.  
  22. 	while(g[state][ch]==-1)
  23. 		state=f[state];
  24.  
  25. 	state=g[state][ch];
  26.  
  27. 	return isEnd[state]?1:0;
  28. }
  29. llu fun(int state,int indx,int flag1,int flag2,int isput){
  30.  
  31. 	if(indx==n){
  32.  
  33. 		if(flag2==1 && isput==1)return 1;
  34. 		else
  35. 			return 0;
  36. 	}
  37.     llu ans=0;
  38. 	if(visited[state][indx][flag1][flag2][isput]!=-1)
  39. 		return dp[state][indx][flag1][flag2][isput];
  40.  
  41. 	int max=9;
  42. 	if(flag1==0)max=s[indx]-'0';
  43. 	int min=0;
  44.  
  45.  
  46.  
  47. 	if(flag2==1){
  48. 		for(int i=min;i<=max;i++){
  49.  
  50. 			if(i!=max)
  51. 				ans+=fun(state,indx+1,1,1,isput|(i>0));
  52. 			else
  53. 				ans+=fun(state,indx+1,flag1,1,isput|(i>0));
  54. 		}
  55. 	}else{
  56.  
  57. 		for(int i=min;i<=max;i++){
  58.  
  59. 			int cs=state;
  60.             int state1=nextstate(cs,i);
  61.             if(i!=max)
  62.             ans+=fun(cs,indx+1,1,flag2|state1,isput|(i>0));
  63.             else
  64.             ans+=fun(cs,indx+1,flag1,flag2|state1,isput|(i>0));
  65. 		} 
  66. 	}
  67.  
  68. 	visited[state][indx][flag1][flag2][isput]=1;
  69.  
  70. 	return dp[state][indx][flag1][flag2][isput]=ans;
  71.  
  72. }
  73.  
  74. llu fun2222(llu x){
  75. 	s="";
  76. 	memset(visited,-1,sizeof(visited));
  77. 	memset(dp,0,sizeof(dp));
  78. 	while(x){
  79. 		int d=x%10;
  80. 		x=x/10LL;
  81. 		s=to_string(d)+s;
  82. 	}
  83. 	n=s.length();
  84. 	llu ans=fun(0,0,0,0,0);
  85. 	return ans;
  86.  
  87. }
  88.  
  89. void add(int num){
  90. 	int len=str.length();
  91. 	int temp=0;
  92. 	for(int i=0;i<len;i++){
  93. 		int ch=str[i]-'0';
  94. 		if(g[temp][ch]!=-1)
  95. 			temp=g[temp][ch];
  96. 		else
  97. 			temp=g[temp][ch]=states++;
  98. 	}
  99. 	isEnd[temp]=num;
  100. }
  101.  
  102. void make(){
  103.  
  104. 	memset(f,-1,sizeof(f));
  105.  
  106. 	for(int i=0;i<=9;i++){
  107. 		if(g[0][i]!=-1)
  108. 		{
  109. 			f[g[0][i]]=0;
  110. 			q.push(g[0][i]);
  111. 		}
  112. 	}
  113.  
  114. 	for(int i=0;i<=9;i++){
  115. 		if(g[0][i]==-1){
  116. 			g[0][i]=0;
  117. 		}
  118. 	}
  119.  
  120. 	while(!q.empty()){
  121. 		int x=q.front();
  122. 		q.pop();
  123.  
  124.  
  125.  
  126. 		for(int i=0;i<=9;i++){
  127. 			if(g[x][i]!=-1){
  128.  
  129.             int failure=f[x];
  130.             while(g[failure][i]==-1)
  131.             	failure=f[failure];
  132.  
  133.             f[g[x][i]]=g[failure][i];
  134.             q.push(g[x][i]);
  135. 			}
  136. 		}
  137. 	}
  138. }
  139.  
  140. int main() {
  141. 	for (int it = 0; it < 1000; it++) {
  142. 		llu l, r, k;
  143. 		int n;
  144. 		states = 1;
  145. 		memset(isEnd, 0, sizeof(isEnd));
  146. 		// cin >> l >> r >> k >> n;
  147. 		l = rand() + 1, r = rand() + l, k = rand() % (r - l) + 1;
  148. 		n = rand() % 60 + 1;
  149. 		memset(g, -1, sizeof(g));
  150.  
  151. 		vector<string> in;
  152. 		for (int i = 1; i <= n; i++) {
  153. 			// cin >> str;
  154. 			int len = rand() % 18 + 1;
  155. 			str = "";
  156. 			for (int i = 0; i < len; i++) {
  157. 				str += (i == 0 ? rand() % 9 + 1 : rand() % 10) + '0';
  158. 			}
  159. 			in.push_back(str);
  160. 			add(i);
  161. 		}
  162.  
  163. 		make();
  164.  
  165. 		llu low = l;
  166. 		llu high = r;
  167. 		llu ans22 = 0;
  168.  
  169. 		while (low <= high) {
  170. 			llu mid = (low + high) / 2LL;
  171. 			llu ans = fun2222(mid) - fun2222(l - 1);
  172. 			if (ans >= k) {
  173. 				ans22 = mid;
  174. 				high = mid - 1;
  175. 			} else {
  176. 				low = mid + 1;
  177. 			}
  178. 		}
  179.  
  180. 		llu corans = 0;
  181. 		for (llu a = l, cnt = 0; a <= r; a++) {
  182. 			string curs = to_string(a);
  183. 			for (int i = 0; i < n; i++) {
  184. 				if (curs.find(in[i]) != curs.npos) {
  185. 					cnt++;
  186. 					break;
  187. 				}
  188. 			}
  189. 			if (cnt == k) {
  190. 				corans = a;
  191. 				break;
  192. 			}
  193. 		}
  194.  
  195. 		if (ans22 != corans) {
  196. 			cout << l << ' ' << r << ' ' << k << ' ' << n << '\n';
  197. 			for (int i = 0; i < n; i++)
  198. 				cout << in[i] << '\n';
  199.  
  200. 			cout << ans22 << ' ' << corans << '\n';
  201. 			cout << fun2222(corans) << ' ' << fun2222(ans22) << ' '
  202. 					<< fun2222(l - 1) << '\n';
  203. 			return -1;
  204. 		}
  205.  
  206. 		if (ans22 == 0) {
  207. 			cout << "no such number" << endl;
  208. 		} else {
  209. 			cout << ans22 << endl;
  210. 		}
  211. 	}
  212.  
  213. 	return 0;
  214. }
  215.  
Time limit exceeded #stdin #stdout 5s 132800KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wFw8NZ
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!