AtCoder Beginner Contest 445 D

https://atcoder.jp/contests/abc445/tasks/abc445_d

必ず全体の高さか幅と同じピースがあるので、それを配置して残りを全体とします。これを繰り返します。

// Reconstruct Chocolate
#![allow(non_snake_case)]

use std::collections::{HashSet, HashMap};


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

type Point = (usize, usize);
type Rect = (usize, usize);

fn read_rect() -> Rect {
    let v: Vec<usize> = read_vec();
    let (h, w) = (v[0], v[1]);
    (h, w)
}

fn read_input() -> (usize, usize, Vec<Rect>) {
    let v: Vec<usize> = read_vec();
    let (H, W, N) = (v[0], v[1], v[2]);
    let rects: Vec<Rect> = (0..N).map(|_| read_rect()).collect();
    (H, W, rects)
}

fn print_points(points: Vec<Point>) {
    for (x, y) in points {
        println!("{} {}", x+1, y+1)
    }
}

fn F(mut H: usize, mut W: usize, rects: Vec<Rect>) {
    let N = rects.len();
    let mut points: Vec<Point> = vec![(0, 0); N];
    let mut hs: HashMap<usize, HashSet<usize>> = HashMap::new();
    let mut ws: HashMap<usize, HashSet<usize>> = HashMap::new();
    for (i, &rect) in rects.iter().enumerate() {
        let e1 = hs.entry(rect.0).or_insert(HashSet::new());
        (*e1).insert(i);
        let e2 = ws.entry(rect.1).or_insert(HashSet::new());
        (*e2).insert(i);
    }
    
    while !hs.is_empty() {
        if let Some(v) = hs.remove(&H) {
            for i in v {
                let rect = rects[i];
                points[i] = (H-rect.0, W-rect.1);
                if let Some(s) = ws.get_mut(&rect.1) {
                    s.remove(&i);
                    if s.is_empty() {
                        ws.remove(&rect.1);
                    }
                    W -= rect.1
                }
            }
        }
        else if let Some(w) = ws.remove(&W) {
            for i in w {
                let rect = rects[i];
                points[i] = (H-rect.0, W-rect.1);
                if let Some(s) = hs.get_mut(&rect.0) {
                    s.remove(&i);
                    if s.is_empty() {
                        hs.remove(&rect.0);
                    }
                    H -= rect.0
                }
            }
        }
    }
    
    print_points(points)
}

fn main() {
    let (H, W, rects) = read_input();
    F(H, W, rects)
}