Task: | Ruudukko |
Sender: | Hennkka |
Submission time: | 2020-09-05 21:34:12 +0300 |
Language: | Rust |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 16 |
#2 | ACCEPTED | 30 |
#3 | ACCEPTED | 54 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#4 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#5 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#6 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#7 | ACCEPTED | 0.01 s | 2, 3 | details |
#8 | ACCEPTED | 0.01 s | 2, 3 | details |
#9 | ACCEPTED | 0.01 s | 2, 3 | details |
#10 | ACCEPTED | 0.01 s | 2, 3 | details |
#11 | ACCEPTED | 0.01 s | 2, 3 | details |
#12 | ACCEPTED | 0.01 s | 2, 3 | details |
#13 | ACCEPTED | 0.04 s | 3 | details |
#14 | ACCEPTED | 0.06 s | 3 | details |
#15 | ACCEPTED | 0.08 s | 3 | details |
#16 | ACCEPTED | 0.09 s | 3 | details |
#17 | ACCEPTED | 0.09 s | 3 | details |
#18 | ACCEPTED | 0.09 s | 3 | details |
Compiler report
warning: unused import: `std::collections::BTreeSet` --> input/code.rs:1:5 | 1 | use std::collections::BTreeSet; | ^^^^^^^^^^^^^^^^^^^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default warning: unused import: `std::collections::HashSet` --> input/code.rs:2:5 | 2 | use std::collections::HashSet; | ^^^^^^^^^^^^^^^^^^^^^^^^^
Code
use std::collections::BTreeSet;use std::collections::HashSet;use std::io::BufRead;use std::str::FromStr;#[derive(Clone)]struct Bitset(Vec<u64>);impl Bitset {fn with_size(n: usize) -> Self {Self(vec![0; (n + 63) / 64])}fn union(&mut self, other: &Self) {while self.0.len() < other.0.len() {self.0.push(0);}let n = self.0.len().min(other.0.len());for i in 0..n {self.0[i] |= other.0[i];}}fn set(&mut self, i: usize) {let inner = i % 64;let outer = i / 64;while self.0.len() < outer + 1 {self.0.push(0);}self.0[outer] |= 1u64 << inner;}fn shift_left(&mut self, n: usize) {let inner = n % 64;let outer = n / 64;for _ in 0..outer + 1 {self.0.push(0);}for leg in (outer + 1..self.0.len()).rev() {self.0[leg] =(self.0[leg - outer] << inner) | (self.0[leg - outer - 1] >> (64 - inner));}self.0[outer] = self.0[0] << inner;while let Some(0) = self.0.last() {self.0.pop();}}fn count(&self) -> usize {let mut res = 0usize;for i in &self.0 {res += i.count_ones() as usize;}res}}impl Default for Bitset {fn default() -> Self {Self::with_size(0)}}struct Grid<T> {data: Vec<T>,width: usize,height: usize,}impl<T> Grid<T> {fn new(width: usize, height: usize) -> SelfwhereT: Default + Copy,{Self {data: vec![Default::default(); width * height],width,height,}}}impl<T> std::ops::Index<(usize, usize)> for Grid<T> {type Output = T;fn index(&self, index: (usize, usize)) -> &Self::Output {assert!(index.0 < self.width);assert!(index.1 < self.height);&self.data[self.width * index.1 + index.0]}}impl<T> std::ops::IndexMut<(usize, usize)> for Grid<T> {fn index_mut(&mut self, index: (usize, usize)) -> &mut Self::Output {assert!(index.0 < self.width);assert!(index.1 < self.height);&mut self.data[self.width * index.1 + index.0]}}fn solve(grid: Grid<bool>) -> usize {let n = grid.width;let mut possibilities: Vec<Bitset> = Vec::with_capacity(n);for _ in 0..n {possibilities.push(Default::default());}// possibilities[0].insert(1);possibilities[0].set(0);for y in 0..n {if grid[(0, y)] {// let pos = possibilities[0].iter().map(|v| v + 1).collect();possibilities[0].shift_left(1);}let mut prev = possibilities[0].clone();for x in 1..n {// let pos = possibilities[x - 1].union(&possibilities[x]);// possibilities[x] = if grid[(x, y)] {// pos.map(|v| v + 1).collect()// } else {// pos.copied().collect()// };possibilities[x].union(&prev);if grid[(x, y)] {possibilities[x].shift_left(1);}prev = possibilities[x].clone();}}possibilities[n - 1].count()}fn main() {let stdin = std::io::stdin();let stdin = stdin.lock();let mut lines = stdin.lines();let n = usize::from_str(&lines.next().unwrap().unwrap()).unwrap();let mut grid = Grid::new(n, n);for y in 0..n {let line = lines.next().unwrap().unwrap();for (x, c) in line.char_indices() {grid[(x, y)] = c == 'o';}}println!("{}", solve(grid));}#[cfg(test)]mod tests {use super::*;#[test]fn sample_case() {let mut grid = Grid::new(4, 4);grid[(1, 2)] = true;grid[(2, 0)] = true;grid[(3, 2)] = true;assert_eq!(solve(grid), 3);}#[test]fn test_bitset() {let mut a = Bitset::default();a.set(10000);a.set(50000);let mut b = Bitset::default();b.set(10000);b.set(10001);a.union(&b);assert_eq!(a.count(), 3);for i in 0..100 {a.shift_left(1);assert_eq!(a.count(), 3);}}#[test]fn test_time() {use rand::distributions::{Distribution, Uniform};use std::time::{Duration, Instant};const ITERS: u32 = 30;const SIZE: usize = 1000;let mut rng = rand::thread_rng();let dist = Uniform::from(0..SIZE);let mut time = Duration::from_nanos(1);for i in 0..ITERS {let mut grid = Grid::new(SIZE, SIZE);for i in 0..SIZE {grid[(dist.sample(&mut rng), dist.sample(&mut rng))] = true;}std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);let start = Instant::now();std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);solve(grid);std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);let stop = Instant::now();std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);let test_time = (stop - start).as_secs_f64();assert!(test_time < 1.0, "Took time {}", test_time);time += stop - start;}let time = (time / ITERS).as_secs_f64();assert!(time < 1.0, "Average time {}", time);}}
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
10 .......... .......... .......... .......... ... |
correct output |
---|
1 |
user output |
---|
1 |
Test 2
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
10 o.o....... .......... .o...o.oo. ..o...o.oo ... |
correct output |
---|
9 |
user output |
---|
9 |
Test 3
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
10 o......o.. oo.oo..... oooo....oo o.......oo ... |
correct output |
---|
14 |
user output |
---|
14 |
Test 4
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
10 ..ooooo.oo .ooo.o..oo .....ooo.o ooo.ooo.oo ... |
correct output |
---|
12 |
user output |
---|
12 |
Test 5
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
10 oooooooooo ooo....ooo .oo.oo.ooo oooooooooo ... |
correct output |
---|
10 |
user output |
---|
10 |
Test 6
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
10 oooooooooo oooooooooo oooooooooo oooooooooo ... |
correct output |
---|
1 |
user output |
---|
1 |
Test 7
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 ................................. |
correct output |
---|
1 |
user output |
---|
1 |
Test 8
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 .........o.....o.........o..o.... |
correct output |
---|
114 |
user output |
---|
114 |
Test 9
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 oo..oo.oo..o...o..o.o..o......... |
correct output |
---|
151 |
user output |
---|
151 |
Test 10
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 o..o.ooo..oo.o.o.o..o.o..o..oo... |
correct output |
---|
143 |
user output |
---|
143 |
Test 11
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 oo..oooooooooooo.oooo.o.o.oooo... |
correct output |
---|
115 |
user output |
---|
115 |
Test 12
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 oooooooooooooooooooooooooooooo... |
correct output |
---|
1 |
user output |
---|
1 |
Test 13
Group: 3
Verdict: ACCEPTED
input |
---|
1000 ................................. |
correct output |
---|
1 |
user output |
---|
1 |
Test 14
Group: 3
Verdict: ACCEPTED
input |
---|
1000 o..........o...o...o...o......... |
correct output |
---|
1121 |
user output |
---|
1121 |
Test 15
Group: 3
Verdict: ACCEPTED
input |
---|
1000 .o.............o....o.o......o... |
correct output |
---|
1583 |
user output |
---|
1583 |
Test 16
Group: 3
Verdict: ACCEPTED
input |
---|
1000 oooooo.oooooo.....oooo..o...o.... |
correct output |
---|
1574 |
user output |
---|
1574 |
Test 17
Group: 3
Verdict: ACCEPTED
input |
---|
1000 ooooo.oo.oooooooooo...o...oo..... |
correct output |
---|
1147 |
user output |
---|
1147 |
Test 18
Group: 3
Verdict: ACCEPTED
input |
---|
1000 oooooooooooooooooooooooooooooo... |
correct output |
---|
1 |
user output |
---|
1 |