ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1100. Final Standings

Failing Test #3 although stable sort is implemented
Posted by Pzixel 16 May 2018 04:43
I have implemented a stable sort in Rust. I have checked it on task sample array as well as on other sample data that I was generating.

I have implemented simple count sort because of small M. But for some reason it doesn't pass test #3. Any ideas what could be wrong?

```

fn main() {
let stdin = io::stdin();
let mut lines = stdin.lock().lines();
let n: usize = lines.next().unwrap().unwrap().parse().unwrap();
let mut tuples = Vec::with_capacity(n);

for _ in 0..n {
let line = lines.next().unwrap().unwrap();
let mut line = line.split_whitespace();
let id: u32 = line.next().unwrap().parse().unwrap();
let m: u8 = line.next().unwrap().parse().unwrap();
tuples.push((id, m))
}

let tuples = count_sort(&tuples[..]);

for (id, m) in tuples {
println!("{} {}", id, m);
}
}

fn count_sort(input: &[(u32, u8)]) -> Vec<(u32, u8)>  {
let mut freq = [0 as u8; 101];
for &(_, m) in input {
freq[m as usize] += 1;
}

let mut output = unsafe { get_empty_vector(input.len()) };

for i in (1..freq.len()).rev() {
freq[i - 1] += freq[i];
}

for &(id, m) in input.iter().rev() {
let new_freq = freq[m as usize] - 1;
freq[m as usize] = new_freq;
output[new_freq as usize] = (id, m);
}

output
}

unsafe fn get_empty_vector<T>(size: usize) -> Vec<T> {
let mut vec = Vec::with_capacity(size);
let ptr = vec.as_mut_ptr();
std::mem::forget(vec);
let result = Vec::from_raw_parts(ptr, size, size);
result
}

```