#441097 (Rust) No.868 ハイパー部分和問題

提出ソース

結果

問題	No.868 ハイパー部分和問題
ユーザー	akakimidori
提出日時	2020-03-08 15:38:09
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	6,394 ms / 7,000 ms
コード長	6,470 bytes
コンパイル時間	14,570 ms
コンパイル使用メモリ	379,140 KB
実行使用メモリ	10,072 KB
最終ジャッジ日時	2024-11-07 07:06:09
合計ジャッジ時間	138,398 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	1 ms 5,248 KB
testcase_03	AC	1 ms 5,248 KB
testcase_04	AC	1 ms 5,248 KB
testcase_05	AC	1 ms 5,248 KB
testcase_06	AC	1 ms 5,248 KB
testcase_07	AC	1 ms 5,248 KB
testcase_08	AC	1 ms 5,248 KB
testcase_09	AC	1 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	1 ms 5,248 KB
testcase_12	AC	1 ms 5,248 KB
testcase_13	AC	1 ms 5,248 KB
testcase_14	AC	4,997 ms 9,380 KB
testcase_15	AC	3,408 ms 10,072 KB
testcase_16	AC	4,911 ms 9,024 KB
testcase_17	AC	4,839 ms 9,380 KB
testcase_18	AC	5,112 ms 9,548 KB
testcase_19	AC	5,680 ms 8,600 KB
testcase_20	AC	5,209 ms 8,288 KB
testcase_21	AC	6,394 ms 8,452 KB
testcase_22	AC	6,201 ms 8,244 KB
testcase_23	AC	5,075 ms 8,428 KB
testcase_24	AC	6,071 ms 8,088 KB
testcase_25	AC	6,225 ms 8,644 KB
testcase_26	AC	5,742 ms 8,324 KB
testcase_27	AC	4,955 ms 8,232 KB
testcase_28	AC	5,342 ms 8,264 KB
testcase_29	AC	3,619 ms 9,548 KB
testcase_30	AC	5,092 ms 9,460 KB
testcase_31	AC	3,396 ms 9,812 KB
testcase_32	AC	4,932 ms 9,368 KB
testcase_33	AC	4,995 ms 9,500 KB
testcase_34	AC	4,912 ms 9,488 KB
testcase_35	AC	4,849 ms 9,492 KB
testcase_36	AC	5,366 ms 8,528 KB
testcase_37	AC	5,362 ms 8,660 KB
testcase_38	AC	1 ms 5,248 KB
testcase_39	AC	1 ms 5,248 KB

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

ソースコード

raw source code

// ---------- begin BitSet ----------
#[derive(Clone)]
struct BitSet {
    size: usize,
    a: Vec<usize>,
}

fn bit_size() -> usize {
    8 * std::mem::size_of::<usize>()
}

fn quot_rem(n: usize) -> (usize, usize) {
    let w = bit_size();
    (n / w, n % w)
}

#[allow(dead_code)]
impl BitSet {
    fn new(size: usize) -> Self {
        let w = bit_size();
        BitSet {
            size: size,
            a: vec![0; (size + w - 1) / w],
        }
    }
    fn set_at(&mut self, x: usize) {
        assert!(x < self.size);
        let (q, r) = quot_rem(x);
        self.a[q] |= 1 << r;
    }
    fn clear_at(&mut self, x: usize) {
        assert!(x < self.size);
        let (q, r) = quot_rem(x);
        self.a[q] &= !(1 << r);
    }
    fn get_at(&self, x: usize) -> bool {
        if x >= self.size {
            return false;
        }
        let (q, r) = quot_rem(x);
        (self.a[q] >> r) & 1 == 1
    }
    fn any(&self) -> bool {
        self.a.iter().any(|a| *a != 0)
    }
    fn fix(&mut self) {
        let (q, r) = quot_rem(self.size);
        if r != 0 {
            self.a[q] &= (1 << r) - 1;
        }
    }
    fn clear(&mut self) {
        let len = self.a.len();
        self.a.clear();
        self.a.resize(len, 0);
    }
    fn truncate(&mut self, len: usize) {
        if len >= self.size {
            return;
        }
        let w = bit_size();
        self.a.truncate((len + w - 1) / w);
        self.size = len;
        self.fix();
    }
    fn popcnt(&self) -> usize {
        self.a.iter().fold(0, |s, a| s + a.count_ones() as usize)
    }
    fn shift_left(&self, rhs: usize) -> Self {
        let (q, r) = quot_rem(rhs);
        let mut ans = BitSet::new(self.size + rhs);
        if r == 0 {
            for (x, y) in ans.a[q..].iter_mut().zip(self.a.iter()) {
                *x = *y;
            }
        } else {
            let w = bit_size();
            let mut prev = 0;
            for (x, y) in ans.a[q..].iter_mut().zip(self.a.iter()) {
                *x = (*y << r) | (prev >> (w - r));
                prev = *y;
            }
            *ans.a.last_mut().unwrap() |= prev >> (w - r);
        }
        ans.fix();
        ans
    }
    fn shift_right(&self, rhs: usize) -> Self {
        if rhs >= self.size {
            return BitSet::new(1);
        }
        let (q, r) = quot_rem(rhs);
        let mut ans = BitSet::new(self.size - rhs);
        if r == 0 {
            for (x, y) in ans.a.iter_mut().zip(self.a[q..].iter()) {
                *x = *y;
            }
        } else {
            let w = bit_size();
            let mut prev = 0;
            for (x, y) in ans.a.iter_mut().zip(self.a[q..].iter()).rev() {
                *x |= (*y >> r) | (prev << (w - r));
                prev = *y;
            }
        }
        ans.fix();
        ans
    }
    fn bitwise_or(&self, rhs: &Self) -> Self {
        let (x, y) = if self.size >= rhs.size {(self, rhs)} else {(rhs, self)};
        let mut a = x.a.clone();
        for (a, y) in a.iter_mut().zip(y.a.iter()) {
            *a |= *y;
        }
        BitSet {
            size: x.size,
            a: a,
        }
    }
    fn bitwise_and(&self, rhs: &Self) -> Self {
        let (x, y) = if self.size <= rhs.size {(self, rhs)} else {(rhs, self)};
        let mut a = x.a.clone();
        for (a, y) in a.iter_mut().zip(y.a.iter()) {
            *a &= *y;
        }
        BitSet {
            size: x.size,
            a: a,
        }
    }
    fn bitwise_xor(&self, rhs: &Self) -> Self {
        let (x, y) = if self.size >= rhs.size {(self, rhs)} else {(rhs, self)};
        let mut a = x.a.clone();
        for (a, y) in a.iter_mut().zip(y.a.iter()) {
            *a ^= *y;
        }
        BitSet {
            size: x.size,
            a: a,
        }
    }
    fn bitwise_or_assign(&mut self, rhs: &Self) {
        if self.size < rhs.size {
            self.size = rhs.size;
            self.a.resize(rhs.a.len(), 0);
        }
        for (a, b) in self.a.iter_mut().zip(rhs.a.iter()) {
            *a |= *b;
        }
    }
    fn bitwise_and_assign(&mut self, rhs: &Self) {
        if self.size > rhs.size {
            self.size = rhs.size;
            self.a.resize(rhs.a.len(), 0);
        }
        for (a, b) in self.a.iter_mut().zip(rhs.a.iter()) {
            *a &= *b;
        }
    }
    fn bitwise_xor_assign(&mut self, rhs: &Self) {
        if self.size < rhs.size {
            self.size = rhs.size;
            self.a.resize(rhs.a.len(), 0);
        }
        for (a, b) in self.a.iter_mut().zip(rhs.a.iter()) {
            *a ^= *b;
        }
    }
}
// ---------- end BitSet ----------

use std::io::Read;
use std::io::Write;

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let n: usize = it.next().unwrap().parse().unwrap();
    let m: usize = it.next().unwrap().parse().unwrap();
    let mut a = vec![(0usize, 0); n];
    for a in a.iter_mut() {
        a.0 = it.next().unwrap().parse().unwrap();
    }
    let q: usize = it.next().unwrap().parse().unwrap();
    let mut edge = vec![];
    for i in 0..q {
        let x = it.next().unwrap().parse::<usize>().unwrap() - 1;
        let v: usize = it.next().unwrap().parse().unwrap();
        if i > 0 {
            edge.push((a[x].1, i, a[x].0));
        }
        a[x] = (v, i);
    }
    for (a, s) in a {
        edge.push((s, q, a));
    }
    let mut ans = vec![false; q];
    let mut bit = BitSet::new(1);
    bit.set_at(0);
    let mut stack = vec![(0, q, edge, bit)];
    while let Some((l, r, e, mut bit)) = stack.pop() {
        let mid = (l + r) / 2;
        let mut left = vec![];
        let mut right = vec![];
        for (x, y, v) in e {
            if x <= l && r <= y {
                bit = bit.bitwise_or(&bit.shift_left(v));
                bit.truncate(m + 1);
                continue;
            }
            if l < mid {
                left.push((x, y, v));
            }
            if mid < r {
                right.push((x, y, v));
            }
        }
        if l + 1 == r {
            ans[l] = bit.get_at(m);
        } else {
            stack.push((l, mid, left, bit.clone()));
            stack.push((mid, r, right, bit));
        }
    }
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    for a in ans {
        writeln!(out, "{}", a as usize).ok();
    }
}

fn main() {
    run();
}

yukicoder

結果

テストケース

ソースコード