結果

問題 No.1901 bitwise xor convolution (characteristic 2)
ユーザー akakimidori
提出日時 2022-04-11 16:51:27
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 810 ms / 4,000 ms
コード長 2,934 bytes
コンパイル時間 16,089 ms
コンパイル使用メモリ 379,156 KB
実行使用メモリ 83,072 KB
最終ジャッジ日時 2024-11-08 09:12:27
合計ジャッジ時間 23,541 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// ---------- begin Scanner(require delimiter) ----------
mod scanner {
    pub struct Scanner<R> {
        reader: R,
        buf: Vec<u8>,
    }
    #[allow(dead_code)]
    impl<R: std::io::BufRead> Scanner<R> {
        pub fn new(reader: R) -> Self {
            Scanner {
                reader: reader,
                buf: Vec::with_capacity(1024),
            }
        }
        fn read(&mut self, del: u8) {
            self.buf.clear();
            self.reader.read_until(del, &mut self.buf).ok();
            assert!(self.buf.pop().unwrap() == del);
        }
        pub fn next<T: std::str::FromStr>(&mut self, del: u8) -> T {
            self.read(del);
            std::str::from_utf8(&self.buf)
                .unwrap()
                .trim()
                .parse::<T>()
                .ok()
                .unwrap()
        }
        pub fn next_bytes(&mut self, del: u8) -> Vec<u8> {
            self.read(del);
            std::str::from_utf8(&self.buf)
                .unwrap()
                .trim()
                .bytes()
                .collect()
        }
    }
}
// ---------- end scanner(require delimiter) ----------

fn main() {
    let stdin = std::io::stdin();
    let mut sc = scanner::Scanner::new(stdin.lock());
    run(&mut sc);
}

fn run<R: std::io::BufRead>(sc: &mut scanner::Scanner<R>) {
    let n: usize = sc.next(b'\n');
    let mut a = vec![0u32; 32 << n];
    let mut b = vec![0u32; 32 << n];
    for a in a.chunks_exact_mut(32).chain(b.chunks_exact_mut(32)) {
        for (i, a) in a.iter_mut().enumerate() {
            let x = sc.next::<u32>(if i == 31 { b'\n' } else { b' ' });
            *a = x;
        }
    }
    let mut c = vec![0u32; 63 << n];
    rec(&mut c, &mut a, &mut b);
    use std::fmt::*;
    let mut s = String::new();
    for c in c.chunks(63) {
        for i in 0..63 {
            let p = c[i] & 1;
            write!(&mut s, "{} ", p).ok();
        }
        s.pop();
        s.push('\n');
    }
    print!("{}", s);
}

fn rec(c: &mut [u32], a: &mut [u32], b: &mut [u32]) {
    if a.len() == 32 {
        for (i, a) in a.iter().enumerate() {
            for (c, b) in c[i..].iter_mut().zip(b.iter()) {
                *c += *a * *b;
            }
        }
        return;
    }
    let x = c.len() / 2;
    let (cl, cr) = c.split_at_mut(x);
    let y = a.len() / 2;
    let (al, ar) = a.split_at_mut(y);
    let (bl, br) = b.split_at_mut(y);
    for (((al, ar), bl), br) in al
        .iter_mut()
        .zip(ar.iter_mut())
        .zip(bl.iter_mut())
        .zip(br.iter_mut())
    {
        let x = *al + *ar;
        let y = *al - *ar;
        *al = x;
        *ar = y;
        let x = *bl + *br;
        let y = *bl - *br;
        *bl = x;
        *br = y;
    }
    rec(cl, al, bl);
    rec(cr, ar, br);
    for (a, b) in cl.iter_mut().zip(cr) {
        let x = (*a + *b) / 2;
        let y = (*a - *b) / 2;
        *a = x;
        *b = y;
    }
}
0