fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<int> values;
  6. vector<int> assigned_depths;
  7.  
  8. void calculate_depths(int start_idx, int end_idx, int current_depth) {
  9.     if (start_idx > end_idx) {
  10.         return;
  11.     }
  12.  
  13.     int max_val_idx = start_idx;
  14.     for (int i = start_idx + 1; i <= end_idx; ++i) {
  15.         if (values[i] > values[max_val_idx]) {
  16.             max_val_idx = i;
  17.         }
  18.     }
  19.  
  20.     assigned_depths[max_val_idx] = current_depth;
  21.  
  22.     calculate_depths(start_idx, max_val_idx - 1, current_depth + 1);
  23.     calculate_depths(max_val_idx + 1, end_idx, current_depth + 1);
  24. }
  25.  
  26. int main() {
  27.     ios_base::sync_with_stdio(false);
  28.     cin.tie(NULL);
  29.  
  30.     int test_cases;
  31.     cin >> test_cases;
  32.     while (test_cases--) {
  33.         int array_size;
  34.         cin >> array_size;
  35.  
  36.         values.assign(array_size, 0);
  37.         assigned_depths.assign(array_size, 0);
  38.  
  39.         for (int i = 0; i < array_size; ++i) {
  40.             cin >> values[i];
  41.         }
  42.  
  43.         calculate_depths(0, array_size - 1, 0);
  44.  
  45.         for (int i = 0; i < array_size; ++i) {
  46.             cout << assigned_depths[i] << (i == array_size - 1 ? "" : " ");
  47.         }
  48.         cout << endl;
  49.     }
  50.  
  51.     return 0;
  52. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
3
5
3 5 2 1 4
1
1
4
4 3 1 2
stdout
copy 
1 0 2 3 1
0
0 1 3 2
https://ideone.com/6zP1Ol
language:
C++ (gcc 8.3)
created:
10 hours 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!