#853690 (Rust) No.1876 Xor of Sum

提出ソース

結果

問題	No.1876 Xor of Sum
ユーザー	koba-e964
提出日時	2023-03-28 22:13:09
言語	Rust (1.77.0)
結果	AC
実行時間	415 ms / 2,000 ms
コード長	5,062 bytes
コンパイル時間	960 ms
コンパイル使用メモリ	182,356 KB
実行使用メモリ	4,348 KB
最終ジャッジ日時	2023-10-20 15:11:48
合計ジャッジ時間	10,793 ms
ジャッジサーバーID （参考情報）	judge11 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	7 ms 4,348 KB
testcase_01	AC	6 ms 4,348 KB
testcase_02	AC	8 ms 4,348 KB
testcase_03	AC	168 ms 4,348 KB
testcase_04	AC	288 ms 4,348 KB
testcase_05	AC	39 ms 4,348 KB
testcase_06	AC	405 ms 4,348 KB
testcase_07	AC	44 ms 4,348 KB
testcase_08	AC	40 ms 4,348 KB
testcase_09	AC	266 ms 4,348 KB
testcase_10	AC	144 ms 4,348 KB
testcase_11	AC	344 ms 4,348 KB
testcase_12	AC	166 ms 4,348 KB
testcase_13	AC	248 ms 4,348 KB
testcase_14	AC	208 ms 4,348 KB
testcase_15	AC	232 ms 4,348 KB
testcase_16	AC	33 ms 4,348 KB
testcase_17	AC	366 ms 4,348 KB
testcase_18	AC	409 ms 4,348 KB
testcase_19	AC	409 ms 4,348 KB
testcase_20	AC	408 ms 4,348 KB
testcase_21	AC	405 ms 4,348 KB
testcase_22	AC	408 ms 4,348 KB
testcase_23	AC	406 ms 4,348 KB
testcase_24	AC	407 ms 4,348 KB
testcase_25	AC	407 ms 4,348 KB
testcase_26	AC	408 ms 4,348 KB
testcase_27	AC	409 ms 4,348 KB
testcase_28	AC	412 ms 4,348 KB
testcase_29	AC	415 ms 4,348 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes.by_ref().map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr,) => {};
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
    ($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error"));
}

// Verified by https://atcoder.jp/contests/arc084/submissions/3935443
#[derive(Clone)]
struct BitSet {
    size: usize,
    buf: Vec<usize>,
}

impl BitSet {
    // size should be a multiple of bit-size of usize.
    fn new(size: usize) -> Self {
        let w = 8 * std::mem::size_of::<usize>();
        assert_eq!(size & (w - 1), 0);
        let count = size / w;
        BitSet {
            size: size,
            buf: vec![0; count],
        }
    }
    #[allow(unused)]
    fn set(&mut self, idx: usize, val: bool) {
        debug_assert!(idx < self.size);
        let w = 8 * std::mem::size_of::<usize>();
        let idx0 = idx / w;
        let idx1 = idx & (w - 1);
        if val {
            self.buf[idx0] |= 1 << idx1;
        } else {
            self.buf[idx0] &= !(1 << idx1);
        }
    }
    #[allow(unused)]
    fn get(&self, idx: usize) -> bool {
        let w = 8 * std::mem::size_of::<usize>();
        debug_assert!(idx < self.size);
        let idx0 = idx / w;
        let idx1 = idx & (w - 1);
        (self.buf[idx0] >> idx1 & 1) == 1
    }
    #[allow(unused)]
    fn shl(&self, val: usize) -> Self {
        if val >= self.size { return Self::new(self.size); }
        let w = 8 * std::mem::size_of::<usize>();
        let count = self.size / w;
        let sh0 = val / w;
        let sh1 = val & (w - 1);
        let mut ans = Self::new(self.size);
        if sh1 == 0 {
            for i in 0..count - sh0 {
                ans.buf[i + sh0] = self.buf[i];
            }
        } else {
            ans.buf[sh0] = self.buf[0] << sh1;
            for i in 1..count - sh0 {
                ans.buf[i + sh0] = self.buf[i] << sh1
                    | self.buf[i - 1] >> (w - sh1);
            }
        }
        ans
    }
    // Verified by: https://www.hackerrank.com/contests/yfkpo4/challenges/e-strange-clock/submissions/code/1357435235
    #[allow(unused)]
    fn shr(&self, val: usize) -> Self {
        if val >= self.size { return Self::new(self.size); }
        let w = 8 * std::mem::size_of::<usize>();
        let count = self.size / w;
        let sh0 = val / w;
        let sh1 = val & (w - 1);
        let mut ans = Self::new(self.size);
        if sh1 == 0 {
            for i in 0..count - sh0 {
                ans.buf[i] = self.buf[i + sh0];
            }
        } else {
            for i in 0..count - sh0 - 1 {
                ans.buf[i] = self.buf[i + sh0] >> sh1
                    | self.buf[i + sh0 + 1] << (w - sh1);
            }
            ans.buf[count - sh0 - 1] = self.buf[count - 1] >> sh1;
        }
        ans
    }
    #[allow(unused)]
    fn msb(&self) -> Option<usize> {
        let w = 8 * std::mem::size_of::<usize>();
        let count = self.size / w;
        for i in (0..count).rev() {
            let v = self.buf[i];
            if v != 0 {
                return Some(w * i + w - 1 - v.leading_zeros() as usize);
            }
        }
        None
    }
}

// TODO reference is not allowed as rhs
impl std::ops::BitXorAssign for BitSet {
    fn bitxor_assign(&mut self, other: BitSet) {
        debug_assert_eq!(self.size, other.size);
        for i in 0..self.buf.len() {
            self.buf[i] ^= other.buf[i];
        }
    }
}
impl std::ops::BitOrAssign for BitSet {
    fn bitor_assign(&mut self, other: BitSet) {
        debug_assert_eq!(self.size, other.size);
        for i in 0..self.buf.len() {
            self.buf[i] |= other.buf[i];
        }
    }
}

// https://yukicoder.me/problems/no/1876 (3)
// ナップサック問題で、それぞれの重みについてそれを実現する方法の総数の偶奇だけが分かれば良いことに注意すると、bitset で O(N \sum_i A_i/w)。
// Similar problems: https://atcoder.jp/contests/agc020/tasks/agc020_c
fn main() {
    input! {
        n: usize,
        a: [usize; n],
    }
    const W: usize = 4_000_064;
    let mut bs = BitSet::new(W);
    bs.set(0, true);
    for a in a {
        let tmp = bs.shl(a);
        bs ^= tmp;
    }
    let mut ans = 0;
    for i in 0..W {
        if bs.get(i) {
            ans ^= i;
        }
    }
    println!("{}", ans);
}