fork download
copy 
  1. use std::{cmp::Ordering, collections::BinaryHeap};
  2.  
  3. fn main() {
  4.     assert_eq!(solve(&[1, 100, 10, 10000, 1000]), [0, 2, 1, 4, 3]);
  5.     assert_eq!(solve(&[3, 1, 4, 1, 5, 9, 2]), [3, 0, 4, 1, 5, 6, 2]);
  6.     assert_eq!(solve(&[0, 1, 0, 1, 0, 1, 0, 1]), [0, 4, 1, 5, 2, 6, 3, 7]);
  7. }
  8.  
  9. fn solve<T: Ord>(input: &[T]) -> Vec<usize> {
  10.     let len = input.len();
  11.     let mut heap = (0..len)
  12.         .map(|i| BoundIndex(input, i))
  13.         .collect::<BinaryHeap<_>>();
  14.     let mut output = vec![0; len];
  15.     while let Some(bi) = heap.pop() {
  16.         output[bi.1] = heap.len();
  17.     }
  18.     output
  19. }
  20.  
  21. struct BoundIndex<'a, T: Ord>(&'a [T], usize);
  22.  
  23. impl<T: Ord> Ord for BoundIndex<'_, T> {
  24.     fn cmp(&self, other: &Self) -> Ordering {
  25.         (&self.0[self.1], self.1).cmp(&(&other.0[other.1], other.1))
  26.     }
  27. }
  28.  
  29. impl<T: Ord> PartialOrd for BoundIndex<'_, T> {
  30.     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
  31.         Some(self.cmp(other))
  32.     }
  33. }
  34.  
  35. impl<T: Ord> PartialEq for BoundIndex<'_, T> {
  36.     fn eq(&self, other: &Self) -> bool {
  37.         self.cmp(other) == Ordering::Equal
  38.     }
  39. }
  40.  
  41. impl<T: Ord> Eq for BoundIndex<'_, T> {}
  42.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jYX2ws
language:
Rust (rust 1.56)
created:
54 days 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!