結果

問題 No.1901 bitwise xor convolution (characteristic 2)
ユーザー akakimidori
提出日時 2022-04-07 18:53:55
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1,186 ms / 4,000 ms
コード長 3,265 bytes
コンパイル時間 14,290 ms
コンパイル使用メモリ 379,796 KB
実行使用メモリ 148,736 KB
最終ジャッジ日時 2024-11-08 10:09:36
合計ジャッジ時間 22,184 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `std::io::Write`
  --> src/main.rs:58:5
   |
58 | use std::io::Write;
   |     ^^^^^^^^^^^^^^
   |
   = note: `#[warn(unused_imports)]` on by default

ソースコード

diff #
raw source code 

// ---------- begin bitwise transform ----------
pub fn bitwise_transform<T, F>(a: &mut [T], mut f: F)
where
    F: FnMut(&mut T, &mut T),
{
    let n = a.len().trailing_zeros() as usize;
    assert!(a.len() == 1 << n);
    for i in 0..n {
        for a in a.chunks_exact_mut(2 << i) {
            let (x, y) = a.split_at_mut(1 << i);
            for (x, y) in x.iter_mut().zip(y) {
                f(x, y);
            }
        }
    }
}
// ---------- end bitwise transform ----------
// ---------- 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) ----------

use std::io::Write;

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![vec![0usize; 1 << n]; 32];
    let mut b = vec![vec![0usize; 1 << n]; 32];
    for j in 0..(1 << n) {
        for (i, a) in a.iter_mut().enumerate() {
            let x = sc.next::<usize>(if i == 31 { b'\n' } else { b' ' });
            a[j] = x;
        }
    }
    for j in 0..(1 << n) {
        for (i, a) in b.iter_mut().enumerate() {
            let x = sc.next::<usize>(if i == 31 { b'\n' } else { b' ' });
            a[j] = x;
        }
    }
    for a in a.iter_mut().chain(b.iter_mut()) {
        bitwise_transform(a, |a, b| {
            let x = *a + *b;
            let y = *a - *b;
            *a = x;
            *b = y;
        });
    }
    let mut c = vec![vec![0usize; 1 << n]; 63];
    for (i, a) in a.iter().enumerate() {
        for (c, b) in c[i..].iter_mut().zip(b.iter()) {
            for ((c, a), b) in c.iter_mut().zip(a).zip(b) {
                *c += *a * *b;
            }
        }
    }
    for c in c.iter_mut() {
        bitwise_transform(c, |a, b| {
            let x = *a + *b;
            let y = *a - *b;
            *a = x;
            *b = y;
        });
    }
    use std::fmt::*;
    let mut s = String::new();
    for i in 0..(1 << n) {
        for c in c.iter() {
            let p = c[i] >> n & 1;
            write!(&mut s, "{} ", p).ok();
        }
        s.pop();
        s.push('\n');
    }
    print!("{}", s);
}
0