fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void print (vector<int> &arr){
  5. 	int n = arr.size();
  6. 	for(int i = 0; i < n; i++)
  7. 	cout << arr[i] << " ";
  8. }
  9. int main() {
  10. 	int n, k; cin >> n >> k;
  11. 	vector<int> arr(n);
  12. 	for(int i = 0; i < n; i++)
  13. 	cin >> arr[i];
  14.  
  15. 	vector<int> pref(n);
  16. 	pref[0] = 1;
  17. 	for(int i = 1; i < n; i++){
  18. 		if(arr[i] > arr[i-1])
  19. 		pref[i] = pref[i+1];
  20. 		else
  21. 		pref[i] = 1;
  22.  
  23. 		if(pref[i] == k){
  24. 			print(arr);
  25. 			return 0;
  26. 		}
  27. 	}
  28.  
  29. 	vector<int> prefmin(n);
  30. 	int temp = INT_MAX;
  31. 	for(int i = n-1-k; i < n; i++){
  32. 		temp = min(temp, arr[i]);
  33. 		prefmin[i] = temp;
  34. 	}
  35.  
  36. 	int lo = n-1-k;
  37. 	int hi = n-1;
  38. 	while(hi >= n-1-k && lo >= 0){
  39. 		lo--;
  40. 		hi--;
  41.  
  42. 		if(pref[n-2-k] >= (n-1-k)-lo){
  43. 			if(arr[n-1-k] <= prefmin[hi]){
  44.  
  45. 			}
  46. 			else{
  47. 				lo++; hi++;
  48. 				break;
  49. 			}
  50. 		}
  51. 		lo++; hi++; break;
  52. 	}
  53. 	sort(arr.begin()+lo, arr.begin()+lo+k);
  54. 	print(arr);
  55. 	return 0;
  56. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
7 3
7 6 5 1 4 3 2
stdout
copy 
7 6 5 1 3 4 2
https://ideone.com/sF9xjq
language:
C++14 (gcc 8.3)
created:
10 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!