fork download
copy 
  1. /*~~~~~~~~~~~~~~~~~~~~~~~*/
  2. /*						 */
  3. /*						 */
  4. /*						 */
  5. /*		©raisinten		 */
  6. /*		Darshan Sen		 */
  7. /*						 */
  8. /*						 */
  9. /*						 */
  10. /*~~~~~~~~~~~~~~~~~~~~~~~*/
  11.  
  12.  
  13. #include<bits/stdc++.h>
  14.  
  15. using namespace std;
  16.  
  17. #define eb emplace_back
  18. #define pb push_back
  19. #define ins insert
  20. #define mp make_pair
  21. #define len(s) s.length()
  22. #define repii(i,l,r)	for(i = l; i <= r; ++i)
  23. #define repin(i,l,r)	for(i = l; i <  r; ++i)
  24. #define repdi(i,r,l)	for(i = r; i >= l; --i)
  25. #define repdn(i,r,l)	for(i = r; i >  r; --i)
  26. #define endl "\n"
  27. #define all(v) v.begin(), v.end()
  28. #define mem(n,m) memset(n, m, sizeof(n))
  29. #define pii pair<int, int >
  30. #define pll pair<long long ,long long >
  31. #define usuu unordered_set<unsigned >
  32. #define usii unordered_set<int >
  33. #define usll unordered_set<long long >
  34. #define suu set<unsigned >
  35. #define sii set<int >
  36. #define sll set<long long >
  37. #define vec vector
  38. #define vuu vector<unsigned > 
  39. #define vii vector<int > 
  40. #define vbb vector<bool > 
  41. #define vll vector<long long >
  42. #define vlu vector<long long unsigned >
  43. #define mll map<long long , long long >
  44. #ifdef	_WIN32
  45. #define gc	getchar
  46. #else
  47. #define gc	getchar_unlocked
  48. #endif
  49. #define ret return 0
  50. #define what_is(x) cout << #x << " is: " << x << endl;
  51.  
  52. #define boost ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
  53. #define MOD   1000000007
  54. #define PI	  3.14159265358979323846
  55.  
  56. typedef long long   			ll;
  57. typedef long long unsigned		llu;
  58. typedef long double				ldo;
  59. typedef double					db;
  60.  
  61. template <typename T>
  62. void fs (T& x) {
  63. 	x ^= x;
  64. 	bool neg = false;
  65. 	register char ch = gc();
  66. 	while ((ch != '-') and (ch < '0' or ch > '9'))
  67. 		ch = gc();
  68. 	if (ch == '-') {
  69. 		neg = true;
  70. 		ch = gc();
  71. 	}
  72. 	for(; ch >= '0' and ch <= '9'; ch = gc())
  73. 		x = (x << 1) + (x << 3) + ch - 48;
  74. 	if (neg)
  75. 		x *= -1;
  76. }
  77.  
  78. template <typename T>
  79. void showc (T b, T e) {
  80. 	for (auto it = b; it != e; ++it)
  81. 		cout << (*it) << " ";
  82. 	cout << endl;
  83. }
  84.  
  85. ///////////////////////////////////////////////////////////
  86.  
  87. int main()	{
  88. 	#ifdef LOCAL
  89. 	freopen("input.txt", "r", stdin);
  90. 	freopen("output.txt", "w", stdout);
  91. 	#endif
  92.  
  93. 	boost;
  94.  
  95. 	// int T;
  96. 	// fs(T);
  97. 	// while (T--) {
  98. 	// 	int N;
  99. 	// 	fs(N);
  100. 	// 	int i;
  101. 	// 	vii V(N);
  102. 	// 	for (auto& e : V)
  103. 	// 		fs(e);
  104. 	// 	if (N == 1)
  105. 	// 		cout << -1;
  106. 	// 	else
  107. 	// 		if (next_permutation(all(V)))
  108. 	// 			repin (i, 0, N)
  109. 	// 				cout << V[i];
  110. 	// 		else
  111. 	// 			cout << -1;
  112. 	// 	cout << endl;
  113. 	// }
  114.  
  115. 	int T;
  116. 	fs(T);
  117. 	while (T--) {
  118. 		int N;
  119. 		fs(N);
  120. 		int i;
  121. 		stack<int > S;
  122. 		stack<int > temp;
  123. 		stack<int > another;
  124. 		repin (i, 0, N) {
  125. 			int buffer;
  126. 			fs(buffer);
  127. 			S.push(buffer);
  128. 		}
  129. 		if (N == 1) {
  130. 			cout << -1;
  131. 		} else {
  132. 			int var = S.top();
  133. 			S.pop();
  134. 			temp.push(var);
  135.  
  136. 			i = 1;
  137.  
  138. 			while (!S.empty() and S.top() >= temp.top()) {
  139. 				++i;
  140. 				var = S.top();
  141. 				S.pop();
  142. 				temp.push(var);
  143. 			}
  144. 			// temp descending
  145.  
  146. 			if (i == N) {
  147. 				// descending
  148. 				cout << -1;
  149. 			} else {
  150. 				// turning point = less than max(temp)
  151. 				int last = S.top();
  152. 				// what_is(last);
  153. 				S.pop();
  154.  
  155. 				// for output
  156. 				while (!S.empty()) {
  157. 					var = S.top();
  158. 					S.pop();
  159. 					another.push(var);
  160. 				}
  161. 				while (!another.empty()) {
  162. 					var = another.top();
  163. 					another.pop();
  164. 					cout << var;
  165. 				}
  166.  
  167. 				// target = just greater than last
  168. 				int target = 9;
  169. 				while (!temp.empty()) {
  170. 					var = temp.top();
  171. 					temp.pop();
  172. 					if (last < var)
  173. 						target = min(target, var);
  174. 					another.push(var);
  175. 				}
  176. 				cout << target;
  177. 				// another ascending
  178.  
  179. 				// cout << " ";
  180.  
  181. 				bool targfound = false;
  182. 				bool lasplaced = false;
  183. 				while (!another.empty()) {
  184. 					var = another.top();
  185.  
  186. 					if (var == target and targfound == false) {
  187. 						targfound = true;
  188. 						another.pop();
  189. 						continue;
  190. 					}
  191.  
  192. 					if (last == min(last, var) and lasplaced == false) {
  193. 						lasplaced = true;
  194. 						cout << last << var;
  195. 						another.pop();
  196. 						continue;
  197. 					}
  198.  
  199. 					another.pop();
  200.  
  201. 					cout << var;
  202. 				}
  203. 				if (lasplaced == false)
  204. 					cout << last;
  205. 			}
  206. 		}
  207. 		cout << endl;
  208. 	}
  209.  
  210. 	ret;
  211. }
Success #stdin #stdout 0s 4360KB
comments (?)
stdin
copy 
7
5
1 5 4 8 3
10
1 4 7 4 5 8 4 1 2 6
1
7
2
8 4
5
2 5 5 5 3
5
4 5 5 5 3
8
1 2 3 5 4 3 2 1
stdout
copy 
15834
1474584162
-1
-1
32555
53455
12412335
https://ideone.com/3DODbk
problem JNEXT, based on SPOJ submission 24288733 (CPP14), 2019-08-24 08:05:01
language:
C++14 (gcc 8.3)
created:
6 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!