fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb(a) push_back(a)
  4. #define mp(a,b) make_pair(a,b)
  5. #define ll long long
  6. #define pii pair<int,int>
  7. #define pll pair<ll,ll>
  8. #define forr(a,b,c) for(int a=b;a<c;a++)
  9. #define forrev(a,b,c) for(int a=b;a>c;a--)
  10. #define all(v) v.begin(),v.end()
  11. #define revall(v) v.rbegin(),v.rend()
  12. #define allk(v,k) v.begin()+k,v.end()
  13. #define revallk(v,k) v.rbegin()+k,v.rend()
  14. #define allkj(v,k,j) v.begin()+k,v.end()-j
  15. #define revallkj(v,k,j) v.rbegin()+j,v.rend()-k
  16. #define ff first
  17. #define ss second
  18. ////////////////////////// non-modifiable /////////////////////////////////
  19.  
  20. #define mod 1000000007
  21. #define eps 1e-9
  22. #define inf INT_MAX
  23. #define infl LONG_LONG_MAX
  24. ll power(ll a,ll n)
  25. {
  26. 	if(a==0)return 0;
  27. 	if(a==1 || n==0)return 1;
  28. 	if(n==1)return a%mod;//can remove mod?
  29. 	ll t=power(a,n/2);
  30. 	t=t*t%mod;
  31. 	if(n&1)return t*a%mod;
  32. 	return t;
  33. }
  34. #define P (int)(2e6)+9
  35. #define FACTORIZE 1
  36. #define DETERMINE 2
  37. /*int primes[P];
  38. void sieve(int prime=2)//2->detects prime, 1->max prime in factorization
  39. {
  40. 	forr(i,2,P-3)
  41. 	{
  42. 		if(!primes[i])
  43. 		for(int j=prime*i;j<P-3;j+=i)primes[j]=i;
  44. 	}
  45. 	//forr(i,1,21)cout<<primes[i]<<" ";cout<<endl;
  46. 	if(prime==2)
  47. 	{
  48. 		forr(i,1,P-3)
  49. 		{
  50. 			primes[i] = ( primes[i] == 0 );
  51. 		}
  52. 	}
  53. 	else
  54. 		primes[1] = 1;
  55. }*/
  56. int popcount(ll a)
  57. {
  58. 	int c=0;
  59. 	while(a)
  60. 	{
  61. 		c++;
  62. 		a-=a&-a;
  63. 	}
  64. 	return c;
  65. }
  66. void factorize(int a)
  67. {
  68.  
  69. }
  70. void update(int tree[],int idx,int val,int maxval)
  71. {
  72. 	for(;idx<=maxval;idx+=idx&-idx)
  73. 	{
  74. 		tree[idx]+=val;
  75. 		//tree[idx]%=mod;
  76. 	}
  77. }
  78. int read(int tree[],int idx)
  79. {
  80. 	ll sum=0;
  81. 	for(;idx>0;idx-=idx&-idx)
  82. 	{
  83. 		sum+=tree[idx];
  84. 		//sum%=mod;
  85. 	}
  86. 	return sum;
  87. }
  88. ////////////////////////// MODIFIABLE /////////////////////////////////////
  89.  
  90. struct node2
  91. {
  92. 	int id,val;
  93. 	node2()
  94. 	{
  95. 		static int ctx=1;
  96. 		id=ctx++;
  97. 	};
  98. 	node2(int a,int b=0,int c=0,int d=0,int e=0,int f=0)
  99. 	{
  100. 		val=a;
  101. 	}
  102. };
  103. struct comp2
  104. {
  105. 	bool operator()(int a,int b)
  106. 	{
  107. 		//return a<b;
  108. 		return b<a;	//min heap	
  109. 	}
  110. };
  111. bool cmp2(int a,int b)
  112. {
  113. 	//return a<b;
  114. 	return b<a;
  115. }
  116.  
  117. struct node
  118. {
  119. 	bool present;
  120. 	node * child[26];
  121. 	node()
  122. 	{
  123.         present = 0;
  124.         forr(i,0,26) child[i] = NULL;
  125. 	};
  126. 	node(int a,int b=0,int c=0,int d=0,int e=0,int f=0)
  127. 	{
  128. 		//val=a;
  129. 	}
  130. };
  131. struct comp
  132. {
  133. 	bool operator()(int a,int b)
  134. 	{
  135. 		//return a<b;
  136. 		return b<a;	//min heap	
  137. 	}
  138. };
  139. bool cmp(int a,int b)
  140. {
  141. 	//return a<b;
  142. 	return b<a;
  143. }
  144. ////////////////////////// custom-defined /////////////////////////////////
  145. #define N 500009
  146. int n,m,a,b,c,d,k,h,w,x,y,p,q,t,ans,res,ma,mi,T,act=0,pas=1,cur,flag,now;
  147. int len[N];
  148. string s[N];
  149.  
  150. node * root;
  151.  
  152. //vector<string> s;
  153. double e,f,z;
  154. vector<int> v[1], vec;
  155. set<int> sett;
  156. typedef map<int,int> Mapp;
  157. Mapp mapp;
  158. ////////////////////////// variable declarations //////////////////////////
  159.  
  160. void print()//for detailed output of [a data structure]
  161. {
  162.  
  163. }
  164. void print2()//for detailed output of [a data structure]
  165. {
  166.  
  167. }
  168. void input()
  169. {
  170. 	ios_base::sync_with_stdio(false);cin.tie(NULL);
  171. 	cin >> n;
  172. 	//scanf("%d",&n);
  173.  
  174. 	//cout << "n=" << n << endl;
  175.  
  176. 	forr(i,1,n+1) cin >> s[i];
  177. 		//scanf("%s",s[i]);
  178.  
  179. 	//forr(i,1,n+1) cout << s[i] << endl;
  180.  
  181. 	//cout << " lol " << endl;
  182. }
  183. node * insert( node * root, string& s, int idx, int length, int sid )
  184. {
  185. 	if( root -> present == 1 )
  186. 	{
  187. 		len[ sid ] = idx;
  188. 		cout << "2sid=" << sid << " len[sid]=" << len[sid] << " idx=" << idx << endl;
  189. 		return root;
  190. 	}
  191.  
  192. 	if( idx == length )
  193. 	{
  194. 		root -> present = 1;
  195. 		return root;
  196. 	}
  197.  
  198. 	forr(i,0,s[idx]-'a')
  199. 		if( root->child[i] != NULL )
  200. 		{
  201. 			len[ sid ] = idx;
  202. 			cout << "sid=" << sid << " len[sid]=" << len[sid] << " i=" << i << endl;
  203. 			cout << root->child[i] << endl;
  204. 			root -> present = 1;
  205. 			return root;
  206. 		}
  207.  
  208. 	//if( root->child[ s[idx] - 'a' ] != NULL &&  )
  209.  
  210. 	if( root->child[ s[idx] - 'a' ] == NULL )
  211. 		root->child[ s[idx] - 'a' ] = (node*) malloc( sizeof( node ) );
  212.  
  213. 	root->child[ s[idx] - 'a' ] = insert( root->child[ s[idx] - 'a' ], s, idx+1, length, sid );
  214.  
  215. 	return root;
  216.  
  217. }
  218. void solve()
  219. {
  220. 	forr(i,1,n+1) len[i] = s[i].length();
  221.  
  222. 	forr(i,1,n+1) cout << len[i] << " "; cout << endl;
  223.  
  224. 	root = (node*) malloc( sizeof( node ) );
  225.  
  226. 	root->present = 0;
  227.  
  228. 	forrev(i,n,0)
  229. 	{
  230. 		root = insert( root, s[i], 1, len[i], i );
  231. 	}
  232.  
  233. 	forr(i,1,n+1) cout << len[i] << " "; cout << endl;
  234. }
  235. char buff[500009] = {0};
  236. int id = 0;
  237. void output()
  238. {
  239.  
  240.  
  241.     forr(i,1,n+1) cout << len[i] << " "; cout << endl;
  242.  
  243. 	forr(i,1,n+1)
  244. 	{
  245. 		forr(j,0,len[i])
  246. 			//buffer[id++] = s[i][j];
  247. 			printf("%c",s[i][j]);
  248.  
  249. 		//buffer[id++] = '\n';
  250. 		printf("\n");
  251. 		//cout << string( s[i].begin(), s[i].begin() + len[i] ) << endl;
  252. 	}
  253.  
  254. 	//printf("%s\n",buffer);
  255.  
  256. 	buff[ id-1 ] = 0;
  257.  
  258. 	//cout << buffer;
  259. }
  260. ///////////////////////////// my functions ////////////////////////////////
  261.  
  262. int main() 
  263. {
  264. 	input();
  265. 	solve();
  266. 	output();
  267. 	return 0;
  268. }
  269. //// MAIN //// MAIN //// MAIN //// MAIN //// MAIN //// MAIN //// MAIN ////
Success #stdin #stdout 0.01s 34128KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy
https://ideone.com/w9V6KY
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

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!