#1196373 (Rust) No.4 おもりと天秤

• 問題: No.4 おもりと天秤
• ユーザー: T1610
• 提出日時: 2026-11-01 12:19:53
• 言語: Rust (1.99.0 + proconio + num + itertools + ACL)
• 結果: AC
• 実行時間: 1 ms / 5,000 ms
• コード長: 12,285 bytes
• コンパイル時間: 622 ms
• コンパイル使用メモリ: 202,644 KB
• 実行使用メモリ: 9,904 KB
• 最終ジャッジ日時: 2026-11-01 12:19:56
• 合計ジャッジ時間: 3,073 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge4_0

ファイルパターン	結果
other	AC * 23

ソースコード

#![allow(unused_imports)]
use ac_library::{ModInt998244353 as mint, Segtree, dsu, modint};
use itertools::{Itertools, izip};
use my_library::*;
use num::Float;
// use omniswap::swap;
// use permutohedron::LexicalPermutation;
use proconio::{
    fastout, input,
    marker::{Chars, Usize1},
};
use std::{
    cmp::Reverse,
    collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet},
};

// #[fastout]
fn main() {
    input! {
        n : usize,
        w : [usize; n]
    }
    let sum = w.iter().sum::<usize>();
    if sum % 2 == 1 {
        println!("impossible");
        return;
    }
    let mut d = vec![false; sum / 2 + 1];
    d[0] = true;
    for w in w {
        for i in (w..=sum / 2).rev() {
            d[i] |= d[i - w];
        }
    }
    yes_no2(*d.last().unwrap(), "possible", "impossible");
}

#[allow(dead_code)]
mod my_library {
    use itertools::Itertools;
    use num::Bounded;
    // Utils
    pub fn yes_no(f: bool) {
        yes_no2(f, "Yes", "No");
    }
    pub fn yes_no2<T: std::fmt::Display>(f: bool, yes: T, no: T) {
        println!("{}", if f { yes } else { no });
    }
    pub fn print_vec<T: std::fmt::Display>(s: Vec<T>, sep: &str) {
        println!("{}", s.iter().join(sep));
    }
    pub trait ChangeMinMax {
        /// self より other が小さければ self を更新し、true を返す
        fn chmin(&mut self, other: Self) -> bool;
        /// self より other が大きければ self を更新し、true を返す
        fn chmax(&mut self, other: Self) -> bool;
    }

    // PartialOrd（順序比較可能）なすべての型に一括実装
    impl<T: PartialOrd> ChangeMinMax for T {
        fn chmin(&mut self, other: Self) -> bool {
            if other < *self {
                *self = other;
                true
            } else {
                false
            }
        }

        fn chmax(&mut self, other: Self) -> bool {
            if other > *self {
                *self = other;
                true
            } else {
                false
            }
        }
    }
    pub fn print_vec_usize1(s: Vec<usize>, sep: &str) {
        let s = s.iter().map(|s| s + 1).collect_vec();
        print_vec(s, sep);
    }
    pub fn tenti<T: Copy>(matrix: &Vec<Vec<T>>) -> Vec<Vec<T>> {
        if matrix.is_empty() {
            return Vec::new();
        }
        let h = matrix.len();
        let w = matrix[0].len();
        if w == 0 {
            return Vec::new();
        }
        let mut res = vec![Vec::with_capacity(h); w];
        for i in 0..h {
            for j in 0..w {
                res[j].push(matrix[i][j]);
            }
        }
        res
    }
    pub fn rotate_mat<T: Copy>(matrix: &Vec<Vec<T>>, dy: usize, dx: usize) -> Vec<Vec<T>> {
        if matrix.is_empty() {
            return Vec::new();
        }
        let h = matrix.len();
        let w = matrix[0].len();
        if w == 0 {
            return Vec::new();
        }
        let mut res = matrix.clone();
        res.rotate_left(dy);
        for i in 0..h {
            res[i].rotate_left(dx);
        }
        res
    }

    // Number Theory, Math
    pub fn gcd(a: u64, b: u64) -> u64 {
        if b == 0 { a } else { gcd(b, a % b) }
    }
    pub fn gcd_vec(v: &Vec<u64>) -> u64 {
        v.iter().fold(v[0], |f, x| gcd(*x, f))
    }
    pub fn lcm(a: u64, b: u64) -> u64 {
        a / gcd(a, b) * b
    }
    pub fn lcm_vec(v: &Vec<u64>) -> u64 {
        v.iter().fold(v[0], |f, x| lcm(*x, f))
    }
    pub fn prime_factors(mut n: u64) -> Vec<(u64, u32)> {
        let mut factors = Vec::new();

        // 2 の素因数を処理
        let count_2 = n.trailing_zeros();
        if count_2 > 0 {
            factors.push((2, count_2));
            n >>= count_2;
        }

        // 3 以上の奇数で試し割り
        let mut d = 3;
        while d * d <= n {
            if n % d == 0 {
                let mut count = 0;
                while n % d == 0 {
                    count += 1;
                    n /= d;
                }
                factors.push((d, count));
            }
            d += 2;
        }

        // 残った数が 1 より大きければ、それ自体が素数
        if n > 1 {
            factors.push((n, 1));
        }

        factors
    }

    // Graph

    // Grid
    /* 使用例:
       input! {
           h: usize,
           w: usize,
           s: [Chars; h],
       }
       // 2次元VecをフラットにしてGrid構造体へ変換
       let flattened: Vec<char> = s.into_iter().flatten().collect();
       let grid = Grid::from_vec(flattened, h, w);

        grid[(y, x)]でアクセスできる!!
    */
    use std::ops::{Index, IndexMut};
    #[derive(Clone, Debug)]
    pub struct Grid<T> {
        pub height: usize,
        pub width: usize,
        pub data: Vec<T>,
    }

    impl<T> Grid<T> {
        /// 指定されたサイズと初期値でグリッドを作成
        pub fn new(height: usize, width: usize, init: T) -> Self
        where
            T: Clone,
        {
            Self {
                height,
                width,
                data: vec![init; height * width],
            }
        }
        /// 1次元のVecから作成
        pub fn from_vec(data: Vec<T>, height: usize, width: usize) -> Self {
            assert_eq!(height * width, data.len());
            Self {
                height,
                width,
                data,
            }
        }
        /// 座標 (r, c) がグリッド内か判定
        #[inline]
        pub fn in_bounds(&self, r: isize, c: isize) -> bool {
            r >= 0 && r < self.height as isize && c >= 0 && c < self.width as isize
        }
        /// 座標 (r, c) に対応する1次元インデックスを取得
        #[inline]
        pub fn idx(&self, r: usize, c: usize) -> usize {
            r * self.width + c
        }
        /// 安全に要素を取得 (範囲外なら None)
        pub fn get(&self, r: isize, c: isize) -> Option<&T> {
            if self.in_bounds(r, c) {
                Some(&self.data[self.idx(r as usize, c as usize)])
            } else {
                None
            }
        }
        /// 指定した座標の「4近傍（上下左右）」の有効な座標を列挙するイテレータを返す
        pub fn neighbors4(&self, r: usize, c: usize) -> impl Iterator<Item = (usize, usize)> + '_ {
            let dr = [0, 0, 1, -1];
            let dc = [1, -1, 0, 0];

            (0..4).filter_map(move |i| {
                let nr = r as isize + dr[i];
                let nc = c as isize + dc[i];
                if self.in_bounds(nr, nc) {
                    Some((nr as usize, nc as usize))
                } else {
                    None
                }
            })
        }
    }
    impl Grid<char> {
        /// グリッドを文字列のベクタ (Vec<String>) に変換して返す
        pub fn to_vec_string(&self) -> Vec<String> {
            self.data
                .chunks(self.width)
                .map(|row| row.iter().collect())
                .collect()
        }
    }
    // grid[(r, c)] でアクセスできるようにする
    impl<T> Index<(usize, usize)> for Grid<T> {
        type Output = T;
        fn index(&self, (r, c): (usize, usize)) -> &Self::Output {
            &self.data[self.idx(r, c)]
        }
    }
    impl<T> IndexMut<(usize, usize)> for Grid<T> {
        fn index_mut(&mut self, (r, c): (usize, usize)) -> &mut Self::Output {
            let idx = self.idx(r, c);
            &mut self.data[idx]
        }
    }
    // セグメントツリー用モノイド
    pub mod segtree_monoid {
        // 使用例:
        // let mut seg = Segtree::<segtree_monoid::Min>::from(vec![1, 2, 3]);
        use ac_library::{MapMonoid, Monoid};
        use std::cmp::{max, min};
        pub struct Min;
        impl Monoid for Min {
            type S = i64;
            fn identity() -> Self::S {
                i64::MAX
            } // 単位元：影響しない最大の値
            fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
                min(*a, *b)
            }
        }
        pub struct Max;
        impl Monoid for Max {
            type S = i64;
            fn identity() -> Self::S {
                i64::MIN
            } // 単位元：影響しない最大の値
            fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
                max(*a, *b)
            }
        }
        pub struct Sum;
        impl Monoid for Sum {
            type S = i64;
            fn identity() -> Self::S {
                0
            }
            fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
                a + b
            }
        }
        pub struct RangeAddMin;
        impl MapMonoid for RangeAddMin {
            type M = Min;
            type F = i64;
            fn identity_map() -> Self::F {
                0
            }
            fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
                if *x == i64::MAX { *x } else { x + f }
            }
            fn composition(f: &Self::F, g: &Self::F) -> Self::F {
                f + g
            }
        }
        pub struct RangeAddMax;
        impl MapMonoid for RangeAddMax {
            type M = Max;
            type F = i64;
            fn identity_map() -> Self::F {
                0
            }
            fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
                if *x == i64::MIN { *x } else { x + f }
            }
            fn composition(f: &Self::F, g: &Self::F) -> Self::F {
                f + g
            }
        }
        pub struct RangeUpdateMin;
        const NO_UPDATE_MAX: i64 = i64::MAX;
        impl MapMonoid for RangeUpdateMin {
            type M = Min;
            type F = i64;
            fn identity_map() -> Self::F {
                NO_UPDATE_MAX
            }
            fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
                if *f == NO_UPDATE_MAX { *x } else { *f }
            }
            fn composition(f: &Self::F, g: &Self::F) -> Self::F {
                if *f == NO_UPDATE_MAX { *g } else { *f }
            }
        }
        pub struct RangeUpdateMax;
        const NO_UPDATE_MIN: i64 = i64::MIN;
        impl MapMonoid for RangeUpdateMax {
            type M = Max;
            type F = i64;
            fn identity_map() -> Self::F {
                NO_UPDATE_MIN
            }
            fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
                if *f == NO_UPDATE_MIN { *x } else { *f }
            }
            fn composition(f: &Self::F, g: &Self::F) -> Self::F {
                if *f == NO_UPDATE_MIN { *g } else { *f }
            }
        }
        pub struct RangeSum;
        impl Monoid for RangeSum {
            type S = (i64, i64);
            fn identity() -> Self::S {
                (0, 0)
            }
            fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
                (a.0 + b.0, a.1 + b.1)
            }
        }
        pub struct RangeAddSum;
        impl MapMonoid for RangeAddSum {
            type M = RangeSum;
            type F = i64;
            fn identity_map() -> Self::F {
                0
            }
            fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
                (x.0 + f * x.1, x.1)
            }
            fn composition(f: &Self::F, g: &Self::F) -> Self::F {
                f + g
            }
        }
        pub struct RangeUpdateSum;
        const NO_UPDATE_SUM: i64 = i64::MIN;
        impl MapMonoid for RangeUpdateSum {
            type M = RangeSum;
            type F = i64;
            fn identity_map() -> Self::F {
                NO_UPDATE_SUM
            }
            fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
                if *f == NO_UPDATE_SUM {
                    *x
                } else {
                    (f * x.1, x.1)
                }
            }
            fn composition(f: &Self::F, g: &Self::F) -> Self::F {
                if *f == NO_UPDATE_SUM { *g } else { *f }
            }
        }
    }
}