ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
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?

use std::io::{self, BufRead};

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);


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