fork download
copy 
  1. #[allow(unused_imports)]
  2. use std::io::{BufWriter, stdin, stdout, Write};
  3. #[derive(Default)]
  4. struct Scanner { buf: Vec<String> }
  5. impl Scanner {
  6.     fn next<T: std::str::FromStr>(&mut self) -> T {
  7.         loop {
  8.             if let Some(tok) = self.buf.pop() {
  9.                 return tok.parse().ok().unwrap();
  10.             }
  11.             let mut s = String::new();
  12.             stdin().read_line(&mut s).unwrap();
  13.             self.buf = s.split_whitespace().rev().map(String::from).collect();
  14.         }
  15.     }
  16. }
  17. #[allow(unused_variables)]
  18. macro_rules! io_init { ($scan:ident,$out:ident) => {
  19.     let mut $scan = Scanner::default();
  20.     let $out = &mut BufWriter::new(stdout());
  21. }}
  22. macro_rules! read { ($scan:ident, $($v:pat => $t:ty),*) => { $(let $v = $scan.next::<$t>();)* }; }
  23.  
  24. fn work(mat: &mut Vec<Vec<u64>>, m: usize, k: usize, kk: usize) {
  25.     let mut row = 0;
  26.     for i in 0..k {
  27.         let block = i >> 6;
  28.         let bit = i & 63;
  29.         let mut found = false;
  30.         for o in row..m {
  31.             if (mat[o][block] >> bit) & 1 == 1 {
  32.                 mat.swap(row, o);
  33.                 found = true;
  34.                 break;
  35.             }
  36.         }
  37.         if !found { continue; }
  38.         for o in 0..m {
  39.             if o != row {
  40.                 if (mat[o][block] >> bit) & 1 == 1 {
  41.                     for q in 0..kk {
  42.                         mat[o][q] ^= mat[row][q];
  43.                     }
  44.                 }
  45.             }
  46.         }
  47.         row += 1;
  48.     }
  49. }
  50.  
  51. fn solve(scan: &mut Scanner, out: &mut BufWriter<std::io::Stdout>) {
  52.     read!(scan, t => usize);
  53.     for _ in 0..t {
  54.         read!(scan, n => usize);
  55.         let s = scan.next::<String>();
  56.         let tt = scan.next::<String>();
  57.         let mut k = n;
  58.         let mut m = 1;
  59.         while k % 2 == 0 {
  60.             m *= 2;
  61.             k /= 2;
  62.         }
  63.         let kk = ((k - 1) >> 6) + 1;
  64.         let mut a = vec![vec![0u64; kk]; m];
  65.         let mut b = vec![vec![0u64; kk]; m];
  66.         for i in 0..m {
  67.             for j in 0..k {
  68.                 if s.as_bytes()[i*k + j] == b'1' {
  69.                     a[i][j>>6] |= 1u64 << (j & 63);
  70.                 }
  71.                 if tt.as_bytes()[i*k + j] == b'1' {
  72.                     b[i][j>>6] |= 1u64 << (j & 63);
  73.                 }
  74.             }
  75.         }
  76.         work(&mut a, m, k, kk);
  77.         work(&mut b, m, k, kk);
  78.         if a == b {
  79.             writeln!(out, "Yes").unwrap();
  80.         } else {
  81.             writeln!(out, "No").unwrap();
  82.         }
  83.     }
  84. }
  85.  
  86. fn main() {
  87.     io_init!(scan, out);
  88.     solve(&mut scan, out);
  89. }
  90.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
3
8
00001001
10101001
8
00000000
00001001
6
010110
100010
stdout
copy 
Yes
No
Yes
https://ideone.com/MubT9j
language:
Rust (rust 1.56)
created:
17 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!