結果

問題 No.3041 非対称じゃんけん
ユーザー nebocco
提出日時 2025-03-14 11:12:00
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1,813 ms / 2,200 ms
コード長 4,206 bytes
コンパイル時間 13,251 ms
コンパイル使用メモリ 402,292 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-14 11:12:27
合計ジャッジ時間 25,912 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `f`
  --> src/main.rs:12:19
   |
12 |         n: usize, f : usize,
   |                   ^ help: if this is intentional, prefix it with an underscore: `_f`
   |
   = note: `#[warn(unused_variables)]` on by default

ソースコード

diff # 

#![allow(dead_code, unused_imports, unused_macros, non_snake_case)]
use std::collections::VecDeque;

use proconio::{
    input, input_interactive,
    marker::{Bytes, Chars, Usize1},
};

const MOD: i64 = 998_244_353;
fn main() {
    input! {
        n: usize, f : usize,
        a: [usize; n],
        b: [usize; n],
        c: [usize; n],
    }

    let mut bitset = BitSet::new(64);
    bitset.set(a[0], true);
    bitset.set(b[0], true);
    bitset.set(c[0], true);

    println!("{}", bitset.pop_count());
    for i in 1..n {
        bitset.size += 64;
        bitset.data.push(0);

        bitset = bitset.clone() << a[i] | bitset.clone() << b[i] | bitset.clone() << c[i];
        println!("{}", bitset.pop_count());
    }
}

use std::ops::{BitAnd, BitOr, BitXor, Not, Shl, Shr};

#[derive(Clone)]
pub struct BitSet {
    data: Vec<u64>,
    size: usize,
}

impl BitSet {
    pub fn new(size: usize) -> Self {
        let data = vec![0; (size >> 6) + 1];
        BitSet { data, size }
    }

    pub fn fill(&mut self) {
        self.data.iter_mut().for_each(|x| *x = !0u64);
    }

    pub fn access(&self, pos: usize) -> bool {
        (self.data[pos >> 6] >> (pos & 63)) & 1 == 1
    }

    pub fn set(&mut self, pos: usize, v: bool) {
        if v {
            self.data[pos >> 6] |= 1 << (pos & 63);
        } else {
            self.data[pos >> 6] &= !(1 << (pos & 63));
        }
    }

    pub fn flip(&mut self, pos: usize) {
        self.data[pos >> 6] ^= 1 << (pos & 63);
    }

    pub fn pop_count(&self) -> u32 {
        self.data.iter().map(|x| x.count_ones()).sum()
    }

    pub fn collect(&self) -> Vec<u64> {
        (0..self.size)
            .filter(|&i| self.access(i))
            .map(|x| x as u64)
            .collect::<Vec<u64>>()
    }

    fn resize(&mut self, l: usize) {
        if self.size > l {
            return;
        }
        self.data.resize((l >> 6) + 1, 0);
        self.size = l;
    }
}

impl BitAnd for BitSet {
    type Output = Self;
    fn bitand(mut self, rhs: Self) -> Self {
        let m = std::cmp::max(self.size, rhs.size);
        self.resize(m);
        for (u, v) in self.data.iter_mut().zip(rhs.data.iter()) {
            *u &= v;
        }
        self
    }
}

impl BitOr for BitSet {
    type Output = Self;
    fn bitor(mut self, rhs: Self) -> Self {
        let m = std::cmp::max(self.size, rhs.size);
        self.resize(m);
        for (u, v) in self.data.iter_mut().zip(rhs.data.iter()) {
            *u |= v;
        }
        self
    }
}

impl BitXor for BitSet {
    type Output = Self;
    fn bitxor(mut self, rhs: Self) -> Self {
        let m = std::cmp::max(self.size, rhs.size);
        self.resize(m);
        for (u, v) in self.data.iter_mut().zip(rhs.data.iter()) {
            *u ^= v;
        }
        self
    }
}

impl Not for BitSet {
    type Output = Self;
    fn not(mut self) -> Self {
        for u in self.data.iter_mut() {
            *u = !*u;
        }
        self
    }
}

impl Shr<usize> for BitSet {
    type Output = Self;
    fn shr(mut self, rhs: usize) -> Self::Output {
        let big = rhs >> 6;
        let sml = (rhs & 63) as u32;
        let mask = (1 << sml) - 1;
        for i in 0..self.data.len() {
            self.data[i] = if i + big < self.data.len() {
                self.data[i + big]
            } else {
                0
            };
        }
        let mut r = 0;
        for i in (0..self.data.len()).rev() {
            let u = self.data[i];
            self.data[i] = (u & !mask | r).rotate_right(sml);
            r = u & mask;
        }
        self
    }
}

impl Shl<usize> for BitSet {
    type Output = Self;
    fn shl(mut self, rhs: usize) -> Self::Output {
        let n = self.data.len();
        let big = rhs >> 6;
        let sml = (rhs & 63) as u32;
        let mask = (1 << sml) - 1;
        for i in (0..n).rev() {
            self.data[i] = if i >= big { self.data[i - big] } else { 0 };
        }
        let mut r = 0;
        for i in 0..n {
            let u = self.data[i].rotate_left(sml);
            self.data[i] = u & !mask | r;
            r = u & mask;
        }
        self.data[n - 1] &= (1 << (self.size & 31)) - 1;
        self
    }
}
0