Hyper-optimize IO in rust solution

1 files changed, 57 insertions, 13 deletions

diff --git a/kattis-kth-alginda-quicksort/src/main.rs b/kattis-kth-alginda-quicksort/src/main.rs
index 67646b3..afb23f7 100644
--- a/kattis-kth-alginda-quicksort/src/main.rs
+++ b/kattis-kth-alginda-quicksort/src/main.rs
@@ -2,27 +2,71 @@
 
 #![feature(test)]
 
-use std::fmt::Write;
-use std::io::{stdin, Read};
+use std::io::{stdin, stdout, Read, Write};
 
 mod radix_sort;
-
 use radix_sort::radix_sort;
 
 fn main() {
     let mut buffer = String::new();
     stdin().lock().read_to_string(&mut buffer).unwrap();
-    let xs: Vec<i32> = buffer
-        .split_ascii_whitespace()
-        .skip(1)
-        .map(|x| x.parse().unwrap())
-        .collect();
+    let mut p = buffer.bytes();
+    let mut n = 0;
+    while let Some(b) = p.next() {
+        if b == b' ' {
+            break;
+        }
+        n *= 10;
+        n += (b - b'0') as usize;
+    }
+    let mut xs = vec![0; n];
+    for i in 0..n {
+        let mut neg = false;
+        let mut x = 0i32;
+        while let Some(b) = p.next() {
+            match b {
+                b' ' | b'\n' => break,
+                b'-' => neg = true,
+                b => {
+                    x *= 10;
+                    x += (b - b'0') as i32;
+                }
+            }
+        }
+        if neg {
+            x = -x;
+        }
+        xs[i] = x;
+    }
 
-    let xs = radix_sort(xs);
+    radix_sort(&mut xs);
 
-    buffer.clear();
-    for x in xs {
-        writeln!(buffer, "{}", x).unwrap();
+    let mut p = buffer.len() - 1;
+    let b = unsafe { buffer.as_mut_vec() };
+    b[p] = b'\n';
+    p -= 1;
+    for i in (0..n).rev() {
+        let x = xs[i];
+        let neg = x < 0;
+        let mut x = if neg { (-x) as u32 } else { x as u32 };
+        loop {
+            b[p] = (x % 10) as u8 + b'0';
+            p -= 1;
+            x /= 10;
+            if x == 0 {
+                break;
+            }
+        }
+        if neg {
+            b[p] = b'-';
+            p -= 1;
+        }
+        if i > 0 {
+            b[p] = b'\n';
+            p -= 1;
+        }
     }
-    print!("{}", buffer);
+    p += 1;
+
+    stdout().lock().write(&b[p..]).unwrap();
 }