Submission #73932292

---

Source Code Expand

use proconio::input;

fn main() {
    input! {
        n: usize,
        coords: [(usize, usize); n],
    }

    let mut points: Vec<(usize, usize, usize)> = coords
        .into_iter()
        .enumerate()
        .map(|(i, (x, y))| (x, y, i + 1))
        .collect();

    points.sort_by_key(|k| k.0);
    let block_size = (n as f64).sqrt() as usize + 1;
    
    let mut path: Vec<usize> = Vec::with_capacity(n);
    let mut i = 0;
    let mut ascending = true;

    while i < n {
        let end = (i + block_size).min(n);
        let mut block: Vec<(usize, usize, usize)> = points[i..end].to_vec();

        if ascending {
            block.sort_by_key(|k| k.1); // Y 昇順
        } else {
            block.sort_by(|a, b| b.1.cmp(&a.1)); // Y 降順
        }

        for p in block {
            path.push(p.2);
        }

        ascending = !ascending;
        i = end;
    }

    let start_idx = path.iter().position(|&x| x == 1).unwrap();
    let mut final_path = Vec::with_capacity(n);
    for k in 0..n {
        final_path.push(path[(start_idx + k) % n]);
    }

    println!(
        "{}",
        final_path
            .iter()
            .map(|x| x.to_string())
            .collect::<Vec<String>>()
            .join(" ")
    );
}

Submission Info

Judge Result