fork download
copy 
  1. /*
  2.  * @author Santosh Kumar Shaw (devsks)
  3.  * @quote "Code like there's no tommorow!"
  4.  */
  5. #include "bits/stdc++.h"
  6. #include <unordered_map>
  7. #define FOR(X,Y) for(ll X = 0; X < Y; X++)
  8. #define ll long long
  9. #define newTrie (myTrie*) calloc(1, sizeof(myTrie))
  10. #define pb push_back
  11.  
  12. using namespace std;
  13. struct myTrie{
  14. 	bool isWord;
  15. 	struct myTrie *next[26];
  16. 	int fq[26];
  17. 	int srtInd[26];
  18. 	ll len[26];
  19. };
  20. ll mod, isfill[26],reg;
  21. string mystr;
  22. char prnstr[200002], ansStr[200002];
  23. void insertTrie(myTrie *root, int start)
  24. {
  25. 	for(int i = start; i < mystr.length(); ++i)
  26. 	{
  27. 		int index = mystr[i]-'a';
  28. 		root->fq[index]+=1;
  29. 		ll valwa = (mystr.length() - i);
  30. 		root->len[index] += ( (valwa*(valwa+1)>>1) + valwa*(i-start));
  31. 		if(root->fq[index]==1)
  32. 		{
  33. 			root->srtInd[index] = i;
  34. 			break;
  35. 		}
  36. 		else
  37. 		{
  38. 			if(root->fq[index]==2 && (root->next[index] == NULL) )
  39. 			{
  40. 				root->next[index] = newTrie;
  41. 				myTrie* child = root->next[index];
  42. 				if(root->srtInd[index]+1 >= mystr.length())
  43. 					child->isWord = true;
  44. 				else
  45. 				{
  46. 					int newInd = root->srtInd[index]+1;
  47. 					char ch = mystr[newInd];
  48. 					child->fq[ch-'a'] +=1;
  49. 					child->srtInd[ch-'a'] = newInd;
  50. 					valwa = (mystr.length() - newInd);
  51. 					child->len[ch-'a'] += ( (valwa*(valwa+1)>>1) + valwa*( i+1 - start));
  52. 				}
  53. 			}
  54. 			root = root->next[index];
  55. 		}
  56. 	}
  57. 	root->isWord = true;
  58. }
  59. char printTrie(myTrie *root, ll level)
  60. {
  61. 	for( int i = 0; i < 26; i++)
  62. 	{
  63. 		if(root->fq[i] == 1 && root->len[i] >= reg )
  64. 		{
  65. 			ll  low = 1, high = (mystr.length() - root->srtInd[i]), mid, ind = -1;
  66. 			while(low<=high)
  67. 			{
  68. 				mid = low+high>>1;
  69. 				ll cal = mid*(mid+1)>>1;
  70. 				cal += (mid*(level));
  71. 				if(cal >= reg)
  72. 				{
  73. 					ind  = mid;
  74. 					high = mid-1;
  75. 				}
  76. 				else
  77. 					low = mid+1;
  78. 			}
  79. 			if(ind > 1)
  80. 			{
  81. 				reg -= ( (ind*(ind-1)>>1) + (ind-1)*level);
  82. 			}
  83. 			if( (reg-1) < level)
  84. 			{
  85. 				return prnstr[reg-1];
  86. 			}
  87. 			else
  88. 			{
  89. 				reg-=level;
  90. 				if(root->srtInd[i] +reg-1> mystr.length())
  91. 					return 'z';
  92. 				//cout<<reg<<" ";
  93.  
  94. 				return mystr[root->srtInd[i] +reg-1];
  95. 			}
  96. 			/*if (root->next[i] == NULL)
  97. 			{
  98. 				root->next[i] = newTrie;
  99. 				myTrie* child = root->next[i];
  100. 				if(root->srtInd[i]+1 == mystr.length())
  101. 					child->isWord = true;
  102. 				else
  103. 				{
  104. 					int newInd = root->srtInd[i]+1;
  105. 					char ch = mystr[newInd];
  106. 					child->fq[ch-'a'] +=1;
  107. 					child->srtInd[ch-'a'] = newInd;
  108. 					ll valwa = (mystr.length() - newInd);
  109. 					child->len[ch-'a'] += ( (valwa*(valwa+1)>>1) + valwa*(level+1));
  110. 				}
  111. 			}*/
  112. 		//	cout<<root->srtInd[i]<<" "<<mystr[root->srtInd[i]]<<" "<<root->len[i]<<"\n";
  113. 		}
  114. 		else if (root->next[i] && root->len[i] >= reg)
  115. 		{
  116. 			prnstr[level] = i + 'a';
  117. 			ll lenwa = root->fq[i] * (level + 1);
  118. 			if(reg > lenwa)
  119. 			{
  120. 				reg-=lenwa;
  121. 				return printTrie(root->next[i], level + 1);
  122. 			}
  123. 			else
  124. 				return prnstr[ (reg-1)%(level+1)];
  125. 		}
  126. 		else
  127. 			reg-=root->len[i];
  128. 	}	
  129. 	return 'z';	
  130.  
  131. }
  132. int main()
  133. {
  134. 	ios_base::sync_with_stdio(false);
  135. 	cin.tie(0);
  136. 	cout.tie(0);
  137. //	cin>>mystr;
  138.  
  139. 	mystr="";
  140. 	for(int i=0;i<200000;i++){
  141. 	  if(i%2)
  142. 	    mystr.pb('a');
  143. 	  else
  144. 	    mystr.pb('b');
  145. 	}
  146. 	// string is of size 10^4 
  147.  
  148. 	vector< myTrie* > myarr(26,nullptr);
  149. 	vector< vector<int> > myarrInd(26);
  150. 	ll charSum[26] = {0};
  151.  
  152. 	FOR(i,mystr.length())
  153. 	{
  154. 		int lkw = mystr.length() - i;
  155. 		myarrInd[mystr[i]-'a'].push_back(i);
  156. 	//	if(myarr[mystr[i]-'a']==nullptr)
  157. 	//			myarr[mystr[i]-'a'] = newTrie;
  158. //		insertTrie(myarr[mystr[i]-'a'], i);
  159. 		charSum[mystr[i]-'a'] += (lkw*(lkw+1)>>1);
  160. 	}
  161. 	/*
  162. 	FOR(i,26)
  163. 	{
  164. 		if(myarr[i]!=nullptr)
  165. 		{
  166. 			for(int q = 1; q <= charSum[i];++q)
  167. 			{
  168. 				reg = q;
  169. 				char ansch = printTrie(myarr[i],0);
  170. 				cout<<ansch;
  171. 			}
  172. 			cout<<"\n";
  173. 		}
  174. 		//break;
  175. 	}
  176. 	return 0;*/
  177.  
  178. 	for(register int i = 1; i < 26; ++i)
  179. 		charSum[i] += charSum[i - 1];
  180.  
  181. 	ll q,myp, myg = 0;
  182. 	cin>>q;
  183. 	FOR(qq, q)
  184. 	{
  185. 		cin>>myp>>mod;
  186. 		reg = (myp*myg)%mod+1;
  187. 		int ind = -1, low = 0, high = 25, mid;
  188. 		while(low <= high)
  189. 		{
  190. 			mid = low+high>>1;
  191. 			if(charSum[mid] >= reg)
  192. 			{
  193. 				ind = mid;
  194. 				high= mid-1; 
  195. 			}
  196. 			else
  197. 				low = mid+1;
  198. 		}
  199.  
  200. 		if(!isfill[ind])
  201. 		{
  202. 			if(myarr[ind]==nullptr)
  203. 				myarr[ind] = newTrie;
  204.  
  205. 			for(auto it = myarrInd[ind].begin(); it!= myarrInd[ind].end(); ++it )
  206. 				insertTrie(myarr[ind], *it);
  207.  
  208. 			isfill[ind]=1;
  209. 		}
  210. 		if(ind > 0)
  211. 			reg -= charSum[ind-1];
  212.  
  213. 		char ch = printTrie(myarr[ind], 0LL);
  214. 		myg += ch;
  215. 		ansStr[qq] = ch;
  216. 	}
  217. 	FOR(qq,q)
  218. 		cout<<ansStr[qq]<<"\n";
  219.     return 0;
  220. }    
  221.  
  222.  
Time limit exceeded #stdin #stdout 5s 141888KB
comments (?)
stdin
copy 
1
0 1
stdout
copy 
Standard output is empty
https://ideone.com/KBhk3v
language:
C++14 (gcc 8.3)
created:
6 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!