Submission #3609444
Source Code Expand
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
let mut next = || { iter.next().unwrap() };
input_inner!{next, $($r)*}
};
($($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:ty) => {
$next().parse::<$t>().expect("Parse error")
};
}
fn main() {
input!{
h: usize, // 縦棒の長さ - 1
w: usize, // 縦棒の本数
k: usize, // 最終的に辿り着かなければならない縦棒は左から何番目か
}
let m = 1_000_000_007;
// a[h][x] h = 上からh列目を通過した直後, x = 左からx番目の縦棒にいる
// その場合の数
let mut a = [[0u64; 1000]; 1000];
a[0][0] = 1;
for h in 1..(h+1) {
for bars in 0u8..(1 << (w-1)) {
// 連結があるならスキップ
if bars & (bars << 1) != 0 {
continue;
}
for x in 0..w {
let left = x > 0 && (bars & (1 << (x-1)) != 0);
let right = x < w-1 && (bars & (1 << x) != 0);
// println!("h = {}, x = {}", h, x);
// println!("bar = {:b}, left = {}, right = {}", bars, left, right);
// 左へ行くか
if left {
a[h][x-1] += a[h-1][x];
a[h][x-1] %= m;
}
// 右へ行くか
else if right {
a[h][x+1] += a[h-1][x];
a[h][x+1] %= m;
}
// まっすぐ降りるか
else {
a[h][x] += a[h-1][x];
a[h][x] %= m;
}
// for x in 0..w {
// print!("{} ", a[h][x]);
// }
// println!("");
}
}
// println!("h = {}, result ...", h);
// for x in 0..w {
// print!("{} ", a[h][x]);
// }
// println!("");
}
println!("{}", a[h][k-1] % m);
}
Submission Info
Submission Time |
|
Task |
D - Number of Amidakuji |
User |
ehasoe82aoes |
Language |
Rust (1.15.1) |
Score |
400 |
Code Size |
3252 Byte |
Status |
AC |
Exec Time |
4 ms |
Memory |
12156 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_06.txt |
All |
in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_06.txt |
Case Name |
Status |
Exec Time |
Memory |
in01.txt |
AC |
4 ms |
12156 KB |
in02.txt |
AC |
4 ms |
12156 KB |
in03.txt |
AC |
4 ms |
12156 KB |
in04.txt |
AC |
4 ms |
12156 KB |
in05.txt |
AC |
4 ms |
12156 KB |
in06.txt |
AC |
4 ms |
12156 KB |
in07.txt |
AC |
4 ms |
12156 KB |
in08.txt |
AC |
4 ms |
12156 KB |
in09.txt |
AC |
4 ms |
12156 KB |
in10.txt |
AC |
4 ms |
12156 KB |
sample_01.txt |
AC |
4 ms |
12156 KB |
sample_02.txt |
AC |
4 ms |
12156 KB |
sample_03.txt |
AC |
4 ms |
12156 KB |
sample_04.txt |
AC |
4 ms |
12156 KB |
sample_05.txt |
AC |
4 ms |
12156 KB |
sample_06.txt |
AC |
4 ms |
12156 KB |