fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6. using namespace __gnu_pbds;
  7. template <class T>
  8. using ordered_set = tree<T, null_type, std::less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  9. const int M = 1e9 + 7;
  10.  
  11. const int N = 2e5 + 10;
  12.  
  13. // 2nd aug Amazon ML Summer OA training
  14.  
  15. void printBinary(int num)
  16. {
  17. 	for (int i = 10; i >= 0; i--)
  18. 	{
  19. 		cout << (num >> i & 1);
  20. 	}
  21. 	cout << endl;
  22. }
  23.  
  24. ll binaryitr(ll a, ll b)
  25. {
  26. 	ll ans = 1;
  27. 	while (b)
  28. 	{
  29. 		if (b & 1)
  30. 		{
  31. 			ans = (ans * a) % M;
  32. 		}
  33. 		a = (a * a) % M;
  34. 		b >>= 1;
  35. 	}
  36. 	return ans;
  37. }
  38.  
  39. ll fact[N], Infact[N];
  40.  
  41. void factandInfact()
  42. {
  43. 	ll cnt = 1;
  44. 	fact[0] = 1;
  45. 	Infact[0] = 1;
  46. 	for (int i = 1; i <= N; i++)
  47. 	{
  48. 		fact[i] = (fact[i - 1] * i) % M;
  49. 		Infact[i] = binaryitr(fact[i], M - 2);
  50. 	}
  51. }
  52.  
  53. ll ncr(ll a, ll b)
  54. {
  55. 	if (b > a)
  56. 		return 0;
  57. 	return (fact[a] * (Infact[b]) % M * Infact[a - b] % M) % M;
  58. }
  59.  
  60. class DisjointSet
  61. {
  62. 	vector<int> rank, par, Size;
  63.  
  64. public:
  65. 	DisjointSet(int n)
  66. 	{
  67. 		rank.resize(n + 1, 0);
  68. 		par.resize(n + 1);
  69. 		Size.resize(n + 1, 1);
  70. 		for (int i = 0; i <= n; i++)
  71. 		{
  72. 			par[i] = i;
  73. 		}
  74. 	}
  75.  
  76. 	int findPar(int node)
  77. 	{
  78. 		if (node == par[node])
  79. 			return node;
  80. 		return par[node] = findPar(par[node]);
  81. 	}
  82.  
  83. 	void UnionByrank(int u, int v)
  84. 	{
  85. 		int ulp_u = findPar(u);
  86. 		int ulp_v = findPar(v);
  87. 		if (ulp_u == ulp_v)
  88. 			return;
  89. 		if (rank[ulp_u] > rank[ulp_v])
  90. 		{
  91. 			par[ulp_v] = ulp_u;
  92. 		}
  93. 		else if (rank[ulp_u] < rank[ulp_v])
  94. 		{
  95. 			par[ulp_u] = ulp_v;
  96. 		}
  97. 		else
  98. 		{
  99. 			par[ulp_v] = ulp_u;
  100. 			rank[ulp_u]++;
  101. 		}
  102. 	}
  103.  
  104. 	void UnionBySize(int u, int v)
  105. 	{
  106. 		int ulp_u = findPar(u);
  107. 		int ulp_v = findPar(v);
  108. 		if (ulp_u == ulp_v)
  109. 			return;
  110. 		if (Size[ulp_u] > Size[ulp_v])
  111. 		{
  112. 			par[ulp_v] = ulp_u;
  113. 			Size[ulp_u] += Size[ulp_v];
  114. 		}
  115. 		else
  116. 		{
  117. 			par[ulp_u] = ulp_v;
  118. 			Size[ulp_v] += Size[ulp_u];
  119. 		}
  120. 	}
  121. };
  122.  
  123. class Node
  124. {
  125. public:
  126. 	Node *links[26];
  127. 	bool flag = false;
  128. 	bool containkey(char ch)
  129. 	{
  130. 		return links[ch - 'a'] != nullptr;
  131. 	}
  132. 	void put(char ch, Node *node)
  133. 	{
  134. 		links[ch - 'a'] = node;
  135. 	}
  136. 	Node *get(char ch)
  137. 	{
  138. 		return links[ch - 'a'];
  139. 	}
  140. 	void setEnd()
  141. 	{
  142. 		flag = true;
  143. 	}
  144. 	bool isEnd()
  145. 	{
  146. 		return flag;
  147. 	}
  148. };
  149.  
  150. class Trie
  151. {
  152. private:
  153. 	Node *root;
  154.  
  155. public:
  156. 	Trie()
  157. 	{
  158. 		root = new Node();
  159. 	}
  160.  
  161. 	void insert(string word)
  162. 	{
  163. 		Node *node = root;
  164. 		for (int i = 0; i < word.size(); i++)
  165. 		{
  166. 			if (!(node->containkey(word[i])))
  167. 			{
  168. 				node->put(word[i], new Node());
  169. 			}
  170. 			node = node->get(word[i]);
  171. 		}
  172. 		node->setEnd();
  173. 	}
  174.  
  175. 	bool search(string word)
  176. 	{
  177. 		Node *node = root;
  178. 		for (int i = 0; i < word.size(); i++)
  179. 		{
  180. 			if (!(node->containkey(word[i])))
  181. 			{
  182. 				return false;
  183. 			}
  184. 			node = node->get(word[i]);
  185. 		}
  186. 		return node->isEnd();
  187. 	}
  188.  
  189. 	bool startsWith(string prefix)
  190. 	{
  191. 		Node *node = root;
  192. 		for (int i = 0; i < prefix.size(); i++)
  193. 		{
  194. 			if (!(node->containkey(prefix[i])))
  195. 			{
  196. 				return false;
  197. 			}
  198. 			node = node->get(prefix[i]);
  199. 		}
  200. 		return true;
  201. 	}
  202. };
  203.  
  204. int main()
  205. {
  206. 	ios_base::sync_with_stdio(false);
  207. 	cin.tie(NULL);
  208. 	string s;
  209. 	cin >> s;
  210. 	map<char, int> mp;
  211. 	stack<char> st;
  212. 	string ans;
  213. 	for (auto ch : s)
  214. 	{
  215. 		mp[ch]++;
  216. 	}
  217. 	for (auto ch : s)
  218. 	{
  219. 		st.push(ch);
  220. 		mp[ch]--;
  221. 		if(mp[ch]==0) mp.erase(ch);
  222. 		while (!st.empty() && mp.size() > 0 && st.top() <= (mp.begin()->first))
  223. 		{
  224. 			char key = st.top();
  225. 			st.pop();
  226. 			ans.push_back(key);
  227. 		}
  228.  
  229.  
  230. 	}
  231.  
  232. 	while (!st.empty())
  233. 	{
  234. 		ans.push_back(st.top());
  235. 		st.pop();
  236. 	}
  237. 	cout << ans << endl;
  238. 	return 0;
  239. }
  240.  
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
bdadbde
stdout
copy 
abddbde
https://ideone.com/AVGOUd
language:
C++14 (gcc 8.3)
created:
17 days 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!