結果

問題 No.1056 2D Lamps
ユーザー koba-e964koba-e964
提出日時 2021-12-19 20:57:18
言語 Rust
(1.77.0 + proconio)
結果
WA  
実行時間 -
コード長 5,385 bytes
コンパイル時間 14,539 ms
コンパイル使用メモリ 378,708 KB
実行使用メモリ 36,608 KB
最終ジャッジ日時 2024-09-15 14:48:03
合計ジャッジ時間 16,629 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: function `find_basis_gf2` is never used
  --> src/main.rs:47:4
   |
47 | fn find_basis_gf2(a: &[Vec<i32>]) -> Vec<(Vec<i32>, Vec<i32>)> {
   |    ^^^^^^^^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: function `naive` is never used
  --> src/main.rs:74:4
   |
74 | fn naive(n: usize) {
   |    ^^^^^

ソースコード

diff #
プレゼンテーションモードにする

#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
($($r:tt)*) => {
let stdin = std::io::stdin();
let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
let mut next = move || -> String{
bytes.by_ref().map(|r|r.unwrap() as char)
.skip_while(|c|c.is_whitespace())
.take_while(|c|!c.is_whitespace())
.collect()
};
input_inner!{next, $($r)*}
};
}
macro_rules! input_inner {
($next:expr) => {};
($next:expr,) => {};
($next:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($next, $t);
input_inner!{$next $($r)*}
};
}
macro_rules! read_value {
($next:expr, ( $($t:tt),* )) => { ($(read_value!($next, $t)),*) };
($next:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
};
($next:expr, chars) => {
read_value!($next, String).chars().collect::<Vec<char>>()
};
($next:expr, usize1) => (read_value!($next, usize) - 1);
($next:expr, [ $t:tt ]) => {{
let len = read_value!($next, usize);
read_value!($next, [$t; len])
}};
($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error"));
}
// (basis, x) where basis = x a
fn find_basis_gf2(a: &[Vec<i32>]) -> Vec<(Vec<i32>, Vec<i32>)> {
let n = a.len();
let m = a[0].len();
let mut basis: Vec<(Vec<_>, Vec<_>)> = vec![];
for i in 0..n {
let mut cur = a[i].to_vec();
let mut real = vec![0; n];
real[i] = 1;
for &(ref b, ref br) in &basis {
let mut xor = cur.clone();
for j in 0..m {
xor[j] ^= b[j];
}
if xor < cur {
cur = xor;
for j in 0..n {
real[j] ^= br[j];
}
}
}
if cur.iter().any(|&x| x != 0) {
basis.push((cur, real));
}
}
basis
}
fn naive(n: usize) {
let mut vs = vec![];
for i in 0..n {
let mut v = vec![0; n * n];
for j in 0..n {
v[i * n + j] = 1;
}
vs.push(v);
}
for i in 0..n {
let mut v = vec![0; n * n];
for j in 0..n {
v[j * n + i] = 1;
}
vs.push(v);
}
for i in 0..2 * n - 1 {
let mut v = vec![0; n * n];
for j in 0..min(n, i + 1) {
let k = i - j;
if k < n {
v[j * n + k] = 1;
}
}
vs.push(v);
}
for i in 0..2 * n - 1 {
let mut v = vec![0; n * n];
for j in 0..min(n, i + 1) {
let k = i - j;
if k < n {
v[j * n + (n - k - 1)] = 1;
}
}
vs.push(v);
}
let b = find_basis_gf2(&vs);
eprintln!("{} => {}", n, b.len());
}
fn red(a: &[Vec<char>]) -> Vec<u64> {
let n = a.len();
let mut v = vec![vec![0; n]; n];
match n {
1 | 2 | 3 => return vec![0],
_ => {}
}
for i in 0..2 {
if v[i][0] == 1 {
for j in 0..n {
v[i][j] ^= 1;
}
}
}
for i in 1..2 {
if v[0][i] == 1 {
for j in 0..n {
v[j][i] ^= 1;
}
}
}
if v[1][1] != 0 {
for i in 0..3 {
let j = 2 - i;
v[i][j] ^= 1;
}
}
for i in 2..n {
if v[1][i] != 0 {
for j in 0..n {
v[j][i] ^= 1;
}
}
if v[i][1] != 0 {
for j in 0..n {
v[i][j] ^= 1;
}
}
if v[0][i] != 0 {
for k in 0..n - i {
v[k][i + k] ^= 1;
}
}
if v[i][0] != 0 {
for k in 0..n - i {
v[i + k][k] ^= 1;
}
}
if v[i][i] != 0 {
for k in 0..min(n, 2 * i + 1) {
if 2 * i - k < n {
v[2 * i - k][k] ^= 1;
}
}
}
if v[i - 1][i] != 0 {
for k in 0..min(n, 2 * i) {
if 2 * i - 1 - k < n {
v[2 * i - 1 - k][k] ^= 1;
}
}
}
}
let mut ans = vec![0u64; 625];
for i in 0..n {
for j in 0..n {
if v[i][j] != 0 {
let idx = i * n + j;
ans[idx / 64] |= 1 << (idx % 64);
}
}
}
ans
}
fn main() {
let out = std::io::stdout();
let mut out = BufWriter::new(out.lock());
macro_rules! puts {($($format:tt)*) => (let _ = write!(out,$($format)*););}
#[allow(unused)]
macro_rules! putvec {
($v:expr) => {
for i in 0..$v.len() {
puts!("{}{}", $v[i], if i + 1 == $v.len() {"\n"} else {" "});
}
}
}
input! {
n: usize, m: usize,
a: [[chars; n]; m],
}
let mut b = vec![];
for i in 0..m {
b.push(red(&a[i]));
}
for i in 0..m {
for j in i + 1..m {
puts!("{}", if b[i] == b[j] { "1" } else { "0" });
}
puts!("\n");
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0