#[derive(Clone, Debug)]
struct Row {
    n: u32, b: u32,
    palette: Vec<bool>,
    max_stone: u32,
    width: u32,
    stones: Vec<u32>,
    max_reachable: u32
}

impl Row {
    fn new(n: u32, b: u32) -> Row {
        Self {
            n, b,
            palette: vec![true; n as usize],
            max_stone: n,
            width: 0,
            stones: Vec::with_capacity(n as usize),
            max_reachable: n
        }
    }

    fn with_stone(n: u32, b: u32, s: u32) -> Row {
        let mut stones = Vec::with_capacity(n as usize);
        stones.push(s);
        let max_stone = n - if s == n { 1 } else { 0 };
        Self {
            n, b,
            palette: (1..=n).map(|i| i != s).collect(),
            max_stone: max_stone,
            width: s,
            stones,
            max_reachable: s + max_stone,
        }
    }

    fn update(&mut self, x: u32) -> bool {
        let stone_len = x - self.width;
        if stone_len > self.n || !self.palette[(stone_len - 1) as usize] {
            return false;
        }
        self.width = x;
        self.palette[(stone_len - 1) as usize] = false;
        self.stones.push(stone_len);
        if self.max_stone == stone_len {
            while !self.palette[(self.max_stone - 1) as usize] {
                self.max_stone -= 1;
            }
            self.max_reachable = x + self.max_stone
        } else {
            self.max_reachable += stone_len
        }
        true
    }

    fn undo_update(&mut self) {
        let stone_len = self.stones.pop().unwrap();
        self.width -= stone_len;
        self.palette[(stone_len - 1) as usize] = true;
        if stone_len > self.max_stone {
            self.max_stone = stone_len;
            self.max_reachable = self.width + stone_len
        } else {
            self.max_reachable -= stone_len
        }
    }

    fn complete(&mut self) {
        self.stones.push(self.b - self.width);
    }

    fn output_repeat(&self) {
        for (i, &stone) in self.stones.iter().enumerate() {
            for _ in 0..stone {
                print!("{}", ['-', '*'][i & 1]);
            }
        }
        println!("");
    }

    fn output_numbers(&self) {
        for stone in self.stones.iter() {
            print!("{:2} ", stone);
        }
        println!("");
    }
}

#[derive(Clone, Debug)]
pub struct Wall {
    n: u32, h: u32, b: u32,
    rows: Vec<Row>,
    x: u32,
    min_max_reachable: u32,
    max_reached: u32,
    steps: u32
}

impl Wall {
    pub fn new(n: u32) -> Self {
        let (h, b) = ((n >> 1) + 1, (n * n + n ) >> 1);
        Self {
            n, h, b,
            rows: vec![Row::new(n, b); h as usize],
            x: 1,
            min_max_reachable: n,
            max_reached: 0,
            steps: 0
        }
    }

    fn new_linear(n: u32) -> Self {
        let (h, b) = ((n >> 1) + 1, (n * n + n ) >> 1);
        let rows = (1..=h).map(|i| Row::with_stone(n, b, i)).collect();
        let x = h + 1;
        Self {
            n, h, b,
            rows,
            x,
            min_max_reachable: 1 + n,
            max_reached: n,
            steps: 0
        }
    }

    fn complete(&mut self) {
        for row in self.rows.iter_mut() {
            row.complete()
        }
    }

    fn order_key(&self, index: u32) -> (i32, i32) {
        let row = self.rows.get(index as usize).unwrap();
        let stones = row.stones.len() as i32;
        let width = row.width as i32;
        let max_stone = row.max_stone as i32;
        let index = index as i32;
        //(-max_stone, index)
        let perc = (self.x as f32 / (self.b as f32)) * (self.h as f32);
        let dif = (perc - (index as f32)).abs().round() as i32;
        (-max_stone, dif)
    }

    fn order(&self) -> Vec<u32> {
        //(0..self.h).collect()
        let mut v: Vec<u32> = (0..self.h).collect();
        let b = self.b;
        v.sort_unstable_by_key(|&row| self.order_key(row));
        v
    }

    pub fn solve(&mut self) -> bool {
        self.steps += 1;
        // complete if already nearly complete
        if self.x == self.b {
            self.complete();
            return true;
        }
        let mut row_empty = false;
        let min_max_reachable = self.min_max_reachable;
        for row_index in self.order() {
            if self.rows[row_index as usize].stones.is_empty() {
                if row_empty {
                    break
                }
                row_empty = true;
            }
            let max_reachable = self.rows[row_index as usize].max_reachable;
            if self.rows[row_index as usize].update(self.x) {
                if max_reachable == self.min_max_reachable {
                    self.min_max_reachable = self.rows.iter()
                        .map(|v| v.max_reachable).min()
                        .unwrap();
                }
                if self.min_max_reachable > self.x {
                    self.x += 1;
                    if self.solve() {
                        return true;
                    }
                    self.x -= 1;
                }
                self.min_max_reachable = min_max_reachable;
                self.rows[row_index as usize].undo_update();
            }
        }
        false
    }

    pub fn output(&self) {
        for row in self.rows.iter() {
            row.output_numbers();
        }
    }
}

/*fn main() {
    let mut wall = Wall::new(26);
    wall.solve();
    wall.output();
}*/