#961226 (Rust) No.2672 Subset Xor Sum

• 問題: No.2672 Subset Xor Sum
• ユーザー: powell
• 提出日時: 2024-03-16 11:00:49
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 432 ms / 2,000 ms
• コード長: 3,741 bytes
• コンパイル時間: 865 ms
• コンパイル使用メモリ: 185,964 KB
• 実行使用メモリ: 321,664 KB
• 最終ジャッジ日時: 2024-03-16 17:44:16
• 合計ジャッジ時間: 6,523 ms
• ジャッジサーバーID （参考情報）: judge12 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,676 KB
testcase_01	AC	1 ms; 6,676 KB
testcase_02	AC	2 ms; 6,676 KB
testcase_03	AC	2 ms; 6,676 KB
testcase_04	AC	2 ms; 6,676 KB
testcase_05	AC	2 ms; 6,676 KB
testcase_06	AC	2 ms; 6,676 KB
testcase_07	AC	2 ms; 6,676 KB
testcase_08	AC	2 ms; 6,676 KB
testcase_09	AC	2 ms; 6,676 KB
testcase_10	AC	2 ms; 6,676 KB
testcase_11	AC	1 ms; 6,676 KB
testcase_12	AC	2 ms; 6,676 KB
testcase_13	AC	2 ms; 6,676 KB
testcase_14	AC	2 ms; 6,676 KB
testcase_15	AC	2 ms; 6,676 KB
testcase_16	AC	2 ms; 6,676 KB
testcase_17	AC	1 ms; 6,676 KB
testcase_18	AC	2 ms; 6,676 KB
testcase_19	AC	2 ms; 6,676 KB
testcase_20	AC	2 ms; 6,676 KB
testcase_21	AC	2 ms; 6,676 KB
testcase_22	AC	2 ms; 6,676 KB
testcase_23	AC	2 ms; 6,676 KB
testcase_24	AC	2 ms; 6,676 KB
testcase_25	AC	2 ms; 6,676 KB
testcase_26	AC	12 ms; 11,520 KB
testcase_27	AC	11 ms; 11,520 KB
testcase_28	AC	2 ms; 6,676 KB
testcase_29	AC	2 ms; 6,676 KB
testcase_30	AC	2 ms; 6,676 KB
testcase_31	AC	17 ms; 7,552 KB
testcase_32	AC	8 ms; 6,676 KB
testcase_33	AC	6 ms; 6,676 KB
testcase_34	AC	13 ms; 6,676 KB
testcase_35	AC	17 ms; 7,424 KB
testcase_36	AC	15 ms; 6,676 KB
testcase_37	AC	17 ms; 7,168 KB
testcase_38	AC	9 ms; 6,676 KB
testcase_39	AC	19 ms; 7,936 KB
testcase_40	AC	4 ms; 6,676 KB
testcase_41	AC	11 ms; 6,676 KB
testcase_42	AC	16 ms; 7,168 KB
testcase_43	AC	12 ms; 6,676 KB
testcase_44	AC	18 ms; 8,064 KB
testcase_45	AC	12 ms; 6,676 KB
testcase_46	AC	1 ms; 6,676 KB
testcase_47	AC	425 ms; 321,664 KB
testcase_48	AC	1 ms; 6,676 KB
testcase_49	AC	1 ms; 6,676 KB
testcase_50	AC	1 ms; 6,676 KB
testcase_51	AC	432 ms; 321,664 KB
testcase_52	AC	365 ms; 321,664 KB
testcase_53	AC	365 ms; 321,408 KB
testcase_54	AC	363 ms; 321,408 KB
testcase_55	AC	361 ms; 321,408 KB
testcase_56	AC	1 ms; 6,676 KB
testcase_57	AC	246 ms; 222,464 KB
testcase_58	AC	84 ms; 77,696 KB
testcase_59	AC	1 ms; 6,676 KB
testcase_60	AC	1 ms; 6,676 KB
testcase_61	AC	1 ms; 6,676 KB
testcase_62	AC	157 ms; 138,240 KB
testcase_63	AC	193 ms; 169,088 KB
testcase_64	AC	309 ms; 264,064 KB
testcase_65	AC	86 ms; 78,848 KB
testcase_66	AC	1 ms; 6,676 KB
testcase_67	AC	1 ms; 6,676 KB

コンパイルメッセージ

warning: variable `N` should have a snake case name
 --> Main.rs:4:9
  |
4 |     let N = get!(usize);
  |         ^ help: convert the identifier to snake case: `n`
  |
  = note: `#[warn(non_snake_case)]` on by default

warning: variable `A` should have a snake case name
 --> Main.rs:5:9
  |
5 |     let A = get!(usize;;);
  |         ^ help: convert the identifier to snake case: `a`

warning: 2 warnings emitted

ソースコード

// 5000 < 2^13

fn main() {
    let N = get!(usize);
    let A = get!(usize;;);

    // 総xorが0にならない場合は拒否
    if A.iter().fold(0, |a, b| a ^ b) != 0 {
        println!("No");
        return;
    }

    // 5001 < N の場合
    // 鳩の巣原理より，同じ数字が2つ以上存在する → これをグループにすれば良い
    if N > 5001 {
        println!("Yes");
        return;
    }

    // dp[i][j] := i番目までの部分列の総xorがjになるものの長さの最小値
    let mut dp = vec![vec![INF; SIZE]; N];

    // 初期化
    dp[0][A[0]] = 1;

    for i in 1..N {
        for j in 0..SIZE {
            chmin! {
                dp[i][j],
                dp[i - 1][j],
                dp[i - 1][j ^ A[i]] + 1,
            };
        }
    }

    // debug2D!(dp);

    if dp[N - 1][0] < N {
        println!("Yes");
    } else {
        println!("No");
    }
}

const INF: usize = 1001001001001001001;
const SIZE: usize = 1 << 13;

mod get_macro {
    //! 入力用マクロ
    //! - 参考：[Rustで競技プログラミング スターターキット](https://qiita.com/hatoo@github/items/fa14ad36a1b568d14f3e)
    /// 入力用マクロ
    #[macro_export]
    macro_rules! get {
        ($t:ty) => {
            {
                let mut line = String::new();
                std::io::stdin().read_line(&mut line).unwrap();
                line.trim().parse::<$t>().unwrap()
            }
        };
        ($($t:ty),*) => {
            {
                let mut line = String::new();
                std::io::stdin().read_line(&mut line).unwrap();
                let mut iter = line.split_whitespace();
                (
                    $(iter.next().unwrap().parse::<$t>().unwrap(),)*
                )
            }
        };
        ($t:ty ; $n:expr) => {
            (0..$n).map(|_|
                get_!($t)
            ).collect::<Vec<_>>()
        };
        ($($t:ty),* ; $n:expr) => {
            (0..$n).map(|_|
                get_!($($t),*)
            ).collect::<Vec<_>>()
        };
        ($t:ty ;;) => {
            {
                let mut line = String::new();
                std::io::stdin().read_line(&mut line).unwrap();
                line.split_whitespace()
                    .map(|t| t.parse::<$t>().unwrap())
                    .collect::<Vec<_>>()
            }
        };
        ($t:ty ;; $n:expr) => {
            (0..$n).map(|_|
                get_!($t ;;)
            ).collect::<Vec<_>>()
        };
    }
}

mod debug_macro {
    //! デバッグ用マクロ
    /// デバッグ用マクロ
    #[macro_export]
    macro_rules! debug {
        ( $($val:expr),* $(,)* ) => {{
            #[cfg(debug_assertions)]
            eprintln!( concat!($(stringify!($val), " = {:?}, "),*), $($val),* );
        }};
    }
    /// 配列用マクロ
    #[macro_export]
    macro_rules! debug2D {
        ( $array:expr ) => {{
            #![cfg(debug_assertions)]
            eprintln!("{}: ", stringify!($array));
            for row in &$array {
                eprintln!("{:?}", row);
            }
        }};
    }
}

mod chmin {
    //! chminの実装
    /// `chmin!{x1, x2, ..., xn}`:`x1`,`x2`,...,`xn`のうち最小のものを、`x1`に代入する
    /// - 代入があったとき、`true`を返す
    #[macro_export]
    macro_rules! chmin {
        ( $a:expr, $b:expr $(,)* ) => {{
            if $a > $b {
                $a = $b;
                true
            } else {
                false
            }
        }};
        ( $a:expr, $b:expr, $c:expr $(,$other:expr)* $(,)* ) => {{
            chmin! {
                $a,
                ($b).min($c)
                $(,$other)*
            }
        }};
    }
}