fork download
copy 
  1. #include <iostream>
  2. #include <stack>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. int main() {
  8. 	// your code goes here
  9. 	int T;
  10. 	cin>>T;
  11. 	while(T--){
  12. 		int N;
  13. 		cin>>N;
  14. 		int temp;
  15. 		vector <int> v;
  16. 		for(int i=0;i<N;i++){
  17. 			cin>>temp;
  18. 			v.push_back(temp);
  19. 		}
  20. 		int k=N-2;
  21. 		for(k;v[k]>=v[k+1];k--){}
  22. 		// if the array is in decreasing order than next permutation can not be done
  23. 		if(k==(-1)){
  24. 		    cout<<k<<endl;
  25. 		    continue;
  26. 		}
  27. 		int i=N-2;
  28. 		int last = v[N-1];
  29. 		stack <int> st;
  30. 		st.push(last);
  31. 		v.pop_back();
  32. 		// pushing into the stack until we find a break point 
  33. 		// that is starting from the last element of the array to the element which is 
  34. 		// less than the previous element (the element on the right of it)
  35. 		for(i;i>=0;i--){
  36. 			if(v[i]<st.top()){
  37. 			    temp = v[i];
  38. 			    st.push(v[i]);
  39. 			    v.pop_back();
  40. 			    break;
  41. 			}
  42. 			else{
  43. 			    st.push(v[i]);
  44. 			    v.pop_back();
  45. 			}
  46.  
  47. 		}
  48. 		// making a temparary array to store elements from the stack
  49. 		vector <int> v4u;
  50. 		while(!st.empty()){
  51. 			v4u.push_back(st.top());
  52. 			st.pop();
  53. 		}
  54. 		// sorting the array to get the next element for the breakpoint element
  55. 		// which we have stored in temp
  56. 		sort(v4u.begin(),v4u.end());
  57. 		int pos;
  58. 		int s = v4u.size();
  59. 		// we need to find the position of breakpoint element so we can swap it with 
  60. 		// the last element in the main array i.e. v
  61. 		for(int i=0;i<s;i++){
  62. 		    if(temp<v4u[i]){
  63. 		        pos=i;
  64. 		        break;
  65. 		    }
  66.  
  67. 		}
  68. 		swap(v4u[0],v4u[pos]);
  69. 		sort(v4u.begin()+1, v4u.end());
  70.  
  71. 		for(int i=0;i<s;i++){
  72. 		    v.push_back(v4u[i]);
  73. 		}
  74. 		for(int j=0;j<N;j++){
  75. 			cout<<v[j];
  76. 		}
  77. 		cout<<endl;
  78. 	}
  79. 	return 0;
  80. }
Success #stdin #stdout 0s 5680KB
comments (?)
stdin
copy 
2
5
5 4 3 2 1
7
1 3 1 8 5 4 0
stdout
copy 
-1
1340158
https://ideone.com/Hj8DlD
problem JNEXT, based on SPOJ submission 27770941 (CPP14), 2021-04-23 21:38:49
language:
C++14 (gcc 8.3)
created:
4 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!