結果
問題 | No.1916 Making Palindrome on Gird |
ユーザー |
![]() |
提出日時 | 2022-04-29 22:23:12 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 2,511 ms / 3,000 ms |
コード長 | 7,402 bytes |
コンパイル時間 | 13,041 ms |
コンパイル使用メモリ | 396,780 KB |
実行使用メモリ | 116,480 KB |
最終ジャッジ日時 | 2024-06-29 03:58:23 |
合計ジャッジ時間 | 32,144 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
コンパイルメッセージ
warning: unnecessary parentheses around type --> src/main.rs:73:15 | 73 | fn readi() -> (i64) { | ^ ^ | = note: `#[warn(unused_parens)]` on by default help: remove these parentheses | 73 - fn readi() -> (i64) { 73 + fn readi() -> i64 { |
ソースコード
// -*- coding:utf-8-unix -*-// #![feature(map_first_last)]#![allow(dead_code)]#![allow(unused_imports)]#![allow(unused_macros)]use std::any::Any;use std::cmp::Ordering::*;use std::collections::*;use std::convert::*;use std::convert::{From, Into};use std::error::Error;use std::f64::consts::PI;use std::fmt::Debug;use std::fmt::Display;use std::fs::File;use std::hash::Hash;use std::io::prelude::*;use std::io::*;use std::iter::Filter;use std::marker::Copy;use std::mem::*;use std::ops::Bound::*;use std::ops::RangeBounds;use std::ops::{Add, Mul, Neg, Sub};use std::process;use std::slice::from_raw_parts;use std::str;use std::vec;const INF: i64 = 1223372036854775807;const UINF: usize = INF as usize;// const FINF: f64 = 122337203685.0;const LINF: i64 = 2147483647;const FINF: f64 = LINF as f64;const INF128: i128 = 1223372036854775807000000000000;const MOD: i64 = 1000000007;// const MOD: i64 = 998244353;const UMOD: usize = MOD as usize;const MPI: f64 = 3.14159265358979323846264338327950288f64;// const MOD: i64 = INF;use std::cmp::*;use std::collections::*;use std::io::stdin;use std::io::stdout;use std::io::Write;macro_rules! p {($x:expr) => {println!("{}", $x);};}macro_rules! d {($x:expr) => {println!("{:?}", $x);};}fn main() {solve();}// use str::Chars;#[allow(dead_code)]fn read<T: std::str::FromStr>() -> T {let mut s = String::new();std::io::stdin().read_line(&mut s).ok();s.trim().parse().ok().unwrap()}#[allow(dead_code)]fn readi() -> (i64) {let mut str = String::new();let _ = stdin().read_line(&mut str).unwrap();let mut iter = str.split_whitespace();iter.next().unwrap().parse::<i64>().unwrap()}#[allow(dead_code)]fn read_vec<T: std::str::FromStr>() -> Vec<T> {read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()}#[allow(dead_code)]fn read_mat<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {(0..n).map(|_| read_vec()).collect()}#[allow(dead_code)]fn readii() -> (i64, i64) {let mut str = String::new();let _ = stdin().read_line(&mut str).unwrap();let mut iter = str.split_whitespace();(iter.next().unwrap().parse::<i64>().unwrap(),iter.next().unwrap().parse::<i64>().unwrap(),)}fn readff() -> (f64, f64) {let mut str = String::new();let _ = stdin().read_line(&mut str).unwrap();let mut iter = str.split_whitespace();(iter.next().unwrap().parse::<f64>().unwrap(),iter.next().unwrap().parse::<f64>().unwrap(),)}#[allow(dead_code)]fn readiii() -> (i64, i64, i64) {let mut str = String::new();let _ = stdin().read_line(&mut str).unwrap();let mut iter = str.split_whitespace();(iter.next().unwrap().parse::<i64>().unwrap(),iter.next().unwrap().parse::<i64>().unwrap(),iter.next().unwrap().parse::<i64>().unwrap(),)}#[allow(dead_code)]fn readuu() -> (usize, usize) {let mut str = String::new();let _ = stdin().read_line(&mut str).unwrap();let mut iter = str.split_whitespace();(iter.next().unwrap().parse::<usize>().unwrap(),iter.next().unwrap().parse::<usize>().unwrap(),)}fn readcc() -> (char, char) {let mut str = String::new();let _ = stdin().read_line(&mut str).unwrap();let mut iter = str.split_whitespace();(iter.next().unwrap().parse::<char>().unwrap(),iter.next().unwrap().parse::<char>().unwrap(),)}fn readuuu() -> (usize, usize, usize) {let mut str = String::new();let _ = stdin().read_line(&mut str).unwrap();let mut iter = str.split_whitespace();(iter.next().unwrap().parse::<usize>().unwrap(),iter.next().unwrap().parse::<usize>().unwrap(),iter.next().unwrap().parse::<usize>().unwrap(),)}#[allow(dead_code)]fn readiiii() -> (i64, i64, i64, i64) {let mut str = String::new();let _ = stdin().read_line(&mut str).unwrap();let mut iter = str.split_whitespace();(iter.next().unwrap().parse::<i64>().unwrap(),iter.next().unwrap().parse::<i64>().unwrap(),iter.next().unwrap().parse::<i64>().unwrap(),iter.next().unwrap().parse::<i64>().unwrap(),)}#[allow(dead_code)]fn readuuuu() -> (usize, usize, usize, usize) {let mut str = String::new();let _ = stdin().read_line(&mut str).unwrap();let mut iter = str.split_whitespace();(iter.next().unwrap().parse::<usize>().unwrap(),iter.next().unwrap().parse::<usize>().unwrap(),iter.next().unwrap().parse::<usize>().unwrap(),iter.next().unwrap().parse::<usize>().unwrap(),)}pub fn mod_pow(x: usize, n: usize, m: usize) -> usize {let mut res = 1;let mut x = x % m;let mut n = n;while n > 0 {if n & 1 == 1 {res = (res * x) % m;}x = (x * x) % m;n >>= 1;}res}fn solve() {let (h, w) = readuu();let mut vv: Vec<Vec<char>> = vec![vec!['0' as char; (0) as usize]; (h) as usize];for i in 0..h {let s: String = read();let vvv = s.chars().collect();vv[i] = vvv;}let mut used = BTreeSet::new();let mut data = BTreeMap::new();let mut st = VecDeque::new();st.push_front((0, h * w - 1));data.insert((0, h * w - 1), 1 as usize);let mut res = 0;while !st.is_empty() {let (x, y) = st.pop_back().unwrap();if used.contains(&(x, y)) {continue;}used.insert((x, y));let cnt = *data.entry((x, y)).or_insert(0);let xi = (x / w) as i64;let xj = (x % w) as i64;let yi = (y / w) as i64;let yj = (y % w) as i64;if xi > yi || xj > yj {continue;}if vv[xi as usize][xj as usize] != vv[yi as usize][yj as usize] {continue;}let dxi = vec![1, 1, 0, 0];let dxj = vec![0, 0, 1, 1];let dyi = vec![0, -1, 0, -1];let dyj = vec![-1, 0, -1, 0];if (xi - yi).abs() + (xj - yj).abs() <= 1 {if (xi - yi).abs() + (xj - yj).abs() == 0 {res += (cnt * mod_pow(2, UMOD - 1, UMOD)) % UMOD;} else {res += cnt;}res %= UMOD;continue;}for ii in 0..4 {let nxi = xi + dxi[ii];let nxj = xj + dxj[ii];let nyi = yi + dyi[ii];let nyj = yj + dyj[ii];if nxi >= 0&& nxi < h as i64&& nxj < w as i64&& nxj >= 0&& nyi >= 0&& nyi < h as i64&& nyj < w as i64&& nyj >= 0{if vv[nxi as usize][nxj as usize] == vv[nyi as usize][nyj as usize] {let nx = (nxi * w as i64 + nxj) as usize;let ny = (nyi * w as i64 + nyj) as usize;let ncnt = *data.entry((nx, ny)).or_insert(0);data.insert((nx, ny), (cnt + ncnt) % UMOD);st.push_front((nx, ny));}}}}// let res = *data.entry((h * w - 1, 0)).or_insert(0);println!("{}", res);}