CSES - Putka Open 2020 – 1/5 - Results
Submission details
Task:Ruudukko
Sender:Hennkka
Submission time:2020-09-05 21:34:12 +0300
Language:Rust
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED16
#2ACCEPTED30
#3ACCEPTED54
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.01 s1, 2, 3details
#7ACCEPTED0.01 s2, 3details
#8ACCEPTED0.01 s2, 3details
#9ACCEPTED0.01 s2, 3details
#10ACCEPTED0.01 s2, 3details
#11ACCEPTED0.01 s2, 3details
#12ACCEPTED0.01 s2, 3details
#13ACCEPTED0.04 s3details
#14ACCEPTED0.06 s3details
#15ACCEPTED0.08 s3details
#16ACCEPTED0.09 s3details
#17ACCEPTED0.09 s3details
#18ACCEPTED0.09 s3details

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) -> Self
where
T: 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