fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. int main() {
  6.     int n, k;
  7.     std::cin >> n >> k;
  8.  
  9.     std::vector<int> rocks(n);
  10.     for (int i = 0; i < n; ++i) {
  11.         std::cin >> rocks[i];
  12.     }
  13.  
  14.     // Resultant array which will contain the rocks in the smallest lexicographical order
  15.     std::vector<int> result;
  16.  
  17.     // We need to sort segments where the weight difference is less than or equal to `k`
  18.     int start = 0;
  19.  
  20.     while (start < n) {
  21.         int end = start;
  22.  
  23.         // Find the segment which can be sorted (based on the weight difference condition)
  24.         while (end < n - 1 && std::abs(rocks[end + 1] - rocks[end]) <= k) {
  25.             end++;
  26.         }
  27.  
  28.         // Create a subvector for this segment and sort it
  29.         std::vector<int> segment(rocks.begin() + start, rocks.begin() + end + 1);
  30.         std::sort(segment.begin(), segment.end());
  31.  
  32.         // Append the sorted segment to the result
  33.         result.insert(result.end(), segment.begin(), segment.end());
  34.  
  35.         // Move to the next segment
  36.         start = end + 1;
  37.     }
  38.  
  39.     // Output the result, which should be the smallest lexicographical sequence
  40.     for (int val : result) {
  41.         std::cout << val << "\n";
  42.     }
  43.  
  44.     return 0;
  45. }
  46.  
Success #stdin #stdout 0s 5264KB
comments (?)
stdin
copy 
5 4
9 4 5 6 7
stdout
copy 
9
4
5
6
7
https://ideone.com/ELJi1X
language:
C++14 (gcc 8.3)
created:
21 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!