fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int find_min_cost(vector<int>& a, int k) {
  5.     int n = a.size();
  6.     vector<int> indices;
  7.     vector<pair<int, int>> sorted_a;
  8.     for (int i = 0; i < n; i++) {
  9.         sorted_a.push_back({a[i], i});
  10.     }
  11.     sort(sorted_a.begin(), sorted_a.end());
  12.     set<int> cut_points;
  13.     for (int i = 0; i < k - 1; i++) {
  14.         cut_points.insert(sorted_a[i].second);
  15.     }
  16.     vector<int> b;
  17.     vector<int> subarray;
  18.     int part = 1;
  19.     for (int i = 0; i < n; i++) {
  20.         subarray.push_back(a[i]);
  21.         if (cut_points.count(i) || i == n - 1) {
  22.             if (part % 2 == 0) {
  23.                 b.insert(b.end(), subarray.begin(), subarray.end());
  24.             }
  25.             subarray.clear();
  26.             part++;
  27.         }
  28.     }
  29.  
  30.     // Step 3: Append 0 at the end of b
  31.     b.push_back(0);
  32.  
  33.     // Step 4: Compute the cost
  34.     int cost = 0;
  35.     for (int i = 0; i < b.size(); i++) {
  36.     	cout << b[i] << ' ';
  37.         if (b[i] != i) {
  38.             cost = i;
  39.             break;
  40.         }
  41.     }
  42.     return cost;
  43. }
  44.  
  45. int main() {
  46. 	int t;
  47. 	cin >> t;
  48. 	while(t--){
  49. 	    int n, k;
  50. 	    cin >> n >> k;
  51. 	    vector<int> a(n);
  52. 	    for (int i = 0; i < n; i++) {
  53. 	        cin >> a[i];
  54. 	    }
  55. 	    cout << find_min_cost(a, k) << "\n";
  56. 	}
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
4
3 2
1 1 1
8 8
1 1 2 2 3 3 4 4
5 4
1 1 1 2 2
5 4
1 1 1000000000 2 2
stdout
copy 
1 0
1 0
1 0
1 0
https://ideone.com/KPldMq
language:
C++14 (gcc 8.3)
created:
38 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!