#1145088 (Rust) No.142 単なる配列の操作に関する実装問題

• 問題: No.142 単なる配列の操作に関する実装問題
• ユーザー: cologne
• 提出日時: 2026-01-18 20:09:10
• 言語: Rust (1.92.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 1,604 ms / 5,000 ms
• コード長: 4,414 bytes
• コンパイル時間: 23,227 ms
• コンパイル使用メモリ: 415,936 KB
• 実行使用メモリ: 7,848 KB
• 最終ジャッジ日時: 2026-01-18 20:09:43
• 合計ジャッジ時間: 30,042 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

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

ソースコード

use fio::*;

struct BitSet {
    n: usize,
    arr: Vec<u64>,
}

impl BitSet {
    fn new(n: usize) -> Self {
        BitSet {
            n,
            arr: vec![0; n.div_ceil(64) + 1], // to prevent off-by-1 error, and fill with 0.
        }
    }
    fn set(&mut self, idx: usize, val: bool) {
        assert!((0..self.n).contains(&idx));
        let (idx, rem) = (idx / 64, idx % 64);
        if val {
            self.arr[idx] |= 1u64 << rem;
        } else {
            self.arr[idx] &= !(1u64 << rem);
        }
    }
    fn get(&self, idx: usize) -> bool {
        assert!((0..self.n).contains(&idx));
        let (idx, rem) = (idx / 64, idx % 64);
        (self.arr[idx] & (1u64 << rem)) != 0
    }

    /// arr[s..t] ^= arr[u..v]
    fn rng_xor(&mut self, s: usize, t: usize, u: usize, v: usize) {
        assert!(s < t && t <= self.n && u < v && v <= self.n && t - s == v - u);
        let len = (v - u).div_ceil(64);
        if len == 0 {
            // no-op
            return;
        }
        let mut buf = vec![0u64; len + 1]; // to prevent off-by-1 error.
        // buf = arr[u..v]
        let rem = u % 64;
        if rem == 0 {
            for i in 0..len {
                buf[i] = self.arr[u / 64 + i];
            }
        } else {
            for i in 0..len {
                buf[i] = (self.arr[u / 64 + i] >> rem) | (self.arr[u / 64 + i + 1] << (64 - rem));
            }
        }
        // Ignore the last part if the last_block is not full.
        let last_block = (v - u) % 64;
        if last_block != 0 {
            buf[len - 1] &= (1u64 << last_block) - 1;
        }
        // arr[s..t] ^= buf
        let rem = s % 64;
        if rem == 0 {
            // the last part is filled with 0, so safe to XOR.
            for i in 0..len {
                self.arr[s / 64 + i] ^= buf[i];
            }
        } else {
            self.arr[s / 64] ^= buf[0] << rem;
            for i in 1..=len {
                self.arr[s / 64 + i] ^= (buf[i - 1] >> (64 - rem)) | (buf[i] << rem);
            }
        }
    }
}

fn main() {
    let [n, s, x, y, z] = read_tuple::<usize, 5>();
    let mut bs = BitSet::new(n);
    let mut cur = s;
    bs.set(0, cur % 2 == 1);
    for i in 1..n {
        cur = (x * cur + y) % z;
        bs.set(i, cur % 2 == 1);
    }
    let q = read::<usize>();
    for _ in 0..q {
        let [s, t, u, v] = read_tuple::<usize, 4>();
        bs.rng_xor(u - 1, v, s - 1, t);
    }
    for i in 0..n {
        print!("{}", if bs.get(i) { 'O' } else { 'E' })
    }
}

mod fio {
    use std::{
        cell::RefCell,
        convert::TryInto,
        fmt::Debug,
        io::{BufRead, BufWriter, StdinLock, StdoutLock, stdin, stdout},
        str::FromStr,
    };
    thread_local! {
        pub static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
        pub static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
    }

    #[allow(dead_code)]
    pub fn read<T: FromStr>() -> T
    where
        <T as FromStr>::Err: Debug,
    {
        read_line().parse().unwrap()
    }

    #[allow(dead_code)]
    pub fn read_vec<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        read_line()
            .split_whitespace()
            .map(|x| x.parse().unwrap())
            .collect()
    }

    #[allow(dead_code)]
    pub fn read_tuple<T, const N: usize>() -> [T; N]
    where
        T: FromStr + Debug,
        <T as FromStr>::Err: Debug,
    {
        read_vec::<T>().try_into().unwrap()
    }

    /// whitespace at the end of the line is ignored
    pub fn read_line() -> String {
        let mut s = String::new();
        STDIN.with(|cell| {
            cell.borrow_mut().read_line(&mut s).unwrap();
        });
        String::from_str(s.trim_end()).unwrap()
    }
}

#[macro_export]
macro_rules! print {
    ($($t:tt)*) => {
        fio::STDOUT.with(|cell|{
            use std::io::Write;
            write!(cell.borrow_mut(), $($t)*).unwrap()
        })};
}

#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        fio::STDOUT.with(|cell| {
            use std::io::Write;
            writeln!(cell.borrow_mut(), $($t)*).unwrap()
        })
    };
}

#[macro_export]
macro_rules! flush {
    () => {
        fio::STDOUT.with(|cell| {
            use std::io::Write;
            cell.borrow_mut().flush().unwrap()
        });
    };
}