Random uncommited stuff

1 files changed, 61 insertions, 0 deletions

diff --git a/kattis-open/pickupsticks/src/main.rs b/kattis-open/pickupsticks/src/main.rs
new file mode 100644
index 0000000..e264092
--- /dev/null
+++ b/kattis-open/pickupsticks/src/main.rs
@@ -0,0 +1,61 @@
+use std::{
+    collections::{BTreeSet, HashMap},
+    io::Read,
+    iter::repeat,
+};
+
+fn main() {
+    let mut input = String::new();
+    std::io::stdin().read_to_string(&mut input).unwrap();
+
+    let mut lines = input.lines();
+    let mut nm = lines.next().unwrap().split_ascii_whitespace();
+    let n: usize = nm.next().unwrap().parse().unwrap();
+    let m: usize = nm.next().unwrap().parse().unwrap();
+
+    let mut covers = HashMap::<usize, Vec<usize>>::with_capacity(m);
+    let mut n_above = vec![0usize; n];
+    let mut sticks_at: Vec<BTreeSet<usize>> = repeat(BTreeSet::new()).take(m).collect();
+
+    for i in 0..n {
+        sticks_at[0].insert(i);
+    }
+
+    for mut line in lines.map(str::split_ascii_whitespace) {
+        let a = line.next().unwrap().parse::<usize>().unwrap() - 1;
+        let b = line.next().unwrap().parse::<usize>().unwrap() - 1;
+
+        covers.entry(a).or_default().push(b);
+        sticks_at[n_above[b]].remove(&b);
+        n_above[b] += 1;
+        sticks_at[n_above[b]].insert(b);
+    }
+
+    let mut picks = Vec::with_capacity(n);
+    loop {
+        let stick = if let Some(&s) = sticks_at[0].iter().next() {
+            s
+        } else {
+            break;
+        };
+        sticks_at[0].remove(&stick);
+        picks.push(stick);
+
+        if let Some(c) = covers.get(&stick) {
+            for &b in c {
+                sticks_at[n_above[b]].remove(&b);
+                n_above[b] -= 1;
+                sticks_at[n_above[b]].insert(b);
+            }
+        }
+    }
+
+    if picks.len() != n {
+        println!("IMPOSSIBLE");
+        return;
+    }
+
+    for p in picks {
+        println!("{}", p + 1);
+    }
+}