| Task: | Ruudukko |
| Sender: | Hennkka |
| Submission time: | 2020-11-08 21:52:42 +0200 |
| Language: | Rust |
| Status: | READY |
| Result: | 72 |
| group | verdict | score |
|---|---|---|
| #1 | ACCEPTED | 5 |
| #2 | ACCEPTED | 12 |
| #3 | ACCEPTED | 27 |
| #4 | ACCEPTED | 28 |
| #5 | RUNTIME ERROR | 0 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | ACCEPTED | 0.01 s | 1, 5 | details |
| #2 | ACCEPTED | 0.01 s | 2, 5 | details |
| #3 | ACCEPTED | 0.05 s | 3, 5 | details |
| #4 | ACCEPTED | 0.01 s | 4, 5 | details |
| #5 | RUNTIME ERROR | 0.01 s | 5 | details |
| #6 | RUNTIME ERROR | 0.01 s | 5 | details |
| #7 | ACCEPTED | 0.01 s | 2, 5 | details |
| #8 | ACCEPTED | 0.01 s | 2, 5 | details |
| #9 | ACCEPTED | 0.01 s | 3, 5 | details |
| #10 | ACCEPTED | 0.02 s | 3, 5 | details |
| #11 | ACCEPTED | 0.04 s | 3, 5 | details |
| #12 | ACCEPTED | 0.04 s | 3, 5 | details |
| #13 | ACCEPTED | 0.01 s | 4, 5 | details |
| #14 | RUNTIME ERROR | 0.01 s | 5 | details |
| #15 | ACCEPTED | 0.01 s | 3, 5 | details |
| #16 | RUNTIME ERROR | 0.01 s | 5 | details |
Compiler report
warning: unused import: `rand::prelude::*`
--> input/code.rs:1:5
|
1 | use rand::prelude::*;
| ^^^^^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: value assigned to `y` is never read
--> input/code.rs:215:13
|
215 | y += 1;
| ^
|
= note: `#[warn(unused_assignments)]` on by default
= help: maybe it is overwritten before being read?
warning: value assigned to `y` is never read
--> input/code.rs:218:13
|
218 | y -= 1;
| ^
|
= help: maybe it is overwritten before being read?
warning: unused variable: `left`
--> input/code.rs:412:17
|
412 | let left = fill_left(h, x1, y1);
| ^^^^ help: consider prefixing with an underscore: `_left`
|
= note: `#[warn(unused_variables)]` on by default
warning: unused variable: `right`
--> input/code.rs:413:17
|
413 | let right = fill_left(h, w + 1 - x2, y2).map(|(y,...Code
use rand::prelude::*;
use std::collections::HashSet;
use std::io::BufRead;
fn flip_y(path: String) -> String {
path.chars()
.map(|c| match c {
'U' => 'D',
'D' => 'U',
c => c,
})
.collect()
}
fn flip_x(path: String) -> String {
path.chars()
.map(|c| match c {
'R' => 'L',
'L' => 'R',
c => c,
})
.collect()
}
fn reverse(path: String) -> String {
path.chars()
.rev()
.map(|c| match c {
'R' => 'L',
'L' => 'R',
'U' => 'D',
'D' => 'U',
c => c,
})
.collect()
}
fn swap_xy(path: String) -> String {
path.chars()
.map(|c| match c {
'R' => 'D',
'L' => 'U',
'U' => 'L',
'D' => 'R',
c => c,
})
.collect()
}
fn walk_and_modify<F>(path: String, y1: usize, x1: usize, mut f: F) -> String
where
F: FnMut(usize, usize, usize, usize) -> Option<String>,
{
let mut res = "".to_string();
let mut x = x1;
let mut y = y1;
for c in path.chars() {
let (ny, nx) = match c {
'U' => (y - 1, x),
'D' => (y + 1, x),
'L' => (y, x - 1),
'R' => (y, x + 1),
c => panic!("Invalid action '{}'", c),
};
let r = f(y, x, ny, nx);
match r {
None => res.push(c),
// Some(s) => res = format!("{}|{}|",res,s),
Some(s) => res += &s,
}
x = nx;
y = ny;
}
res
}
fn brute_solve(h: usize, w: usize, y1: usize, x1: usize, y2: usize, x2: usize) -> Option<String> {
// println!("brute_solve{:?}",(h, w, y1, x1, y2, x2) );
fn dfs(
h: usize,
w: usize,
y: usize,
x: usize,
y2: usize,
x2: usize,
d: usize,
visited: &mut Vec<bool>,
failing: &mut HashSet<(usize, usize, Vec<bool>)>,
) -> Option<String> {
// println!("{} {} {}",x,y,d);
if x < 1 || x > w || y < 1 || y > h {
return None;
}
if visited[x - 1 + (y - 1) * w] {
return None;
}
if d == 0 {
assert!(x == x2 && y == y2);
return Some("".to_string());
}
if x == x2 && y == y2 {
return None;
}
if !failing.insert((x, y, visited.clone())) {
return None;
}
visited[x - 1 + (y - 1) * w] = true;
if let Some(res) = dfs(h, w, y, x + 1, y2, x2, d - 1, visited, failing) {
return Some("R".to_string() + &res);
}
if let Some(res) = dfs(h, w, y + 1, x, y2, x2, d - 1, visited, failing) {
return Some("D".to_string() + &res);
}
if let Some(res) = dfs(h, w, y, x - 1, y2, x2, d - 1, visited, failing) {
return Some("L".to_string() + &res);
}
if let Some(res) = dfs(h, w, y - 1, x, y2, x2, d - 1, visited, failing) {
return Some("U".to_string() + &res);
}
visited[x - 1 + (y - 1) * w] = false;
None
}
dfs(
h,
w,
y1,
x1,
y2,
x2,
h * w - 1,
&mut vec![false; h * w],
&mut HashSet::new(),
)
}
fn solve(h: usize, w: usize, y1: usize, x1: usize, y2: usize, x2: usize) -> Option<String> {
assert!(1 <= x1 && x1 <= w);
assert!(1 <= x2 && x2 <= w);
assert!(1 <= y1 && y1 <= h);
assert!(1 <= y2 && y2 <= h);
if y2 < y1 {
return solve(h, w, h + 1 - y1, x1, h + 1 - y2, x2).map(flip_y);
}
if x2 < x1 {
return solve(h, w, y1, w + 1 - x1, y2, w + 1 - x2).map(flip_x);
}
if h == 1 {
if x1 == 1 && x2 == w {
Some("R".repeat(w - 1))
} else {
None
}
} else if h == 2 {
if y1 == 2 {
return solve(h, w, h + 1 - y1, x1, h + 1 - y2, x2).map(flip_y);
}
assert!(y1 == 1);
if x1 == x2 {
if x1 == 1 {
// Go right, down, and then back left
return Some(format!("{}D{}", "R".repeat(w - 1), "L".repeat(w - 1)));
} else if x1 == w {
// Go left, down, and then back right
return Some(format!("{}D{}", "L".repeat(w - 1), "R".repeat(w - 1)));
} else {
return None;
}
}
assert!(x1 < x2);
// Go first left until the left wall, then back, then fill the space in between, right and back left
let mut res = "".to_string();
let mut x = x1;
while x > 1 {
res.push('L');
x -= 1;
}
res.push('D');
while x < x1 {
res.push('R');
x += 1;
}
// Now we need to go up and down until we reach x2, hopefully on the other side
let mut y = 2;
while x + 1 < x2 {
res.push('R');
x += 1;
if y == 1 {
res.push('D');
y += 1;
} else {
res.push('U');
y -= 1;
}
}
// In next step we share x coordinate with x2
res.push('R');
x += 1;
if y == y2 {
// We hit end, this a failure because the other cell in this column is unvisited
return None;
}
// Now we just walk right until wall, go up or down, and then walk back to x2
while x < w {
res.push('R');
x += 1;
}
if y == 1 {
res.push('D');
y += 1;
} else {
res.push('U');
y -= 1;
}
while x > x2 {
res.push('L');
x -= 1;
}
assert!(res.len() == h * w - 1);
Some(res)
} else if h == 3 {
fn fill_left(h: usize, w: usize, y: usize) -> Option<(usize, String)> {
assert!(h == 3);
if y == 2 {
// println!("Reversing");
// If we have path from (2, w) to (1, w), then we also have the reverse path
let foo = fill_left(h, w, 1).filter(|(y, _)| *y == 2);
// println!("{:?}", foo);
foo.map(|(_, p)| (1, reverse(p)))
} else if y == 1 {
let y = if w % 2 == 0 { 2 } else { 3 };
let res = format!(
"{}D{}",
"L".repeat(w - 1),
solve(2, w, 1, 1, y - 1, w).unwrap()
);
Some((y, res))
} else {
assert_eq!(y, 3);
let y = if w % 2 == 0 { 2 } else { 1 };
let res = format!("{}U{}", "L".repeat(w - 1), solve(2, w, 2, 1, y, w).unwrap());
Some((y, res))
}
}
fn fill_left3(w: usize, y1: usize, y2: usize) -> Option<String> {
assert!(y1 != y2);
assert!(w > 0);
if w == 1 {
if y1 == 1 && y2 == 3 {
Some("DD".to_string())
} else if y1 == 3 && y2 == 1 {
Some("UU".to_string())
} else {
None
}
} else {
if y1 == 1 {
if y2 == 2 {
fill_left3(w - 1, 1, 3).map(|p| format!("L{}RU", p))
} else {
assert!(y2 == 3);
fill_left3(w - 1, 1, 2).map(|p| format!("L{}RD", p))
}
} else if y1 == 2 {
if y2 == 1 {
fill_left3(w - 1, 3, 1).map(|p| format!("DL{}R", p))
} else {
assert!(y2 == 3);
fill_left3(w - 1, 1, 3).map(|p| format!("UL{}R", p))
}
} else {
assert!(y1 == 3);
if y2 == 1 {
fill_left3(w - 1, 3, 2).map(|p| format!("L{}RU", p))
} else {
assert!(y2 == 2);
fill_left3(w - 1, 3, 1).map(|p| format!("L{}RD", p))
}
}
}
}
fn fill_right3(w: usize, y1: usize, y2: usize) -> Option<String> {
fill_left3(w, y1, y2).map(flip_x)
}
// if w < 3 {
// return solve(w, h, x1, y1, x2, y2).map(swap_xy);
// }
// Brute small cases
if w <= 4 {
return brute_solve(h, w, y1, x1, y2, x2);
}
// If the endpoints are close to each others, brute the local part and then combine with a solution for ends
if x2 - x1 <= 3 {
let x1_max_extra = (x1 - 1).min(2);
let x2_max_extra = (w - x2).min(2);
for x1_extra in 0..=x1_max_extra {
for x2_extra in 0..=x2_max_extra {
let local_res = brute_solve(
3,
x2 - x1 + 1 + x1_extra + x2_extra,
y1,
x1 + 1 - (x1 - x1_extra),
y2,
x2 + 1 - (x1 - x1_extra),
);
if let Some(local_res) = local_res {
let mut x1_filled = x1 - x1_extra == 1;
let mut x2_filled = x2 + x2_extra == w;
let local_res = walk_and_modify(local_res, y1, x1, |py1, px1, py2, px2| {
if !x1_filled && px1 == x1 - x1_extra && px2 == x1 - x1_extra {
// We are at the left edge, try to fill the left side
if let Some(p) = fill_left3(x1 - 1 - x1_extra, py1, py2)
.map(|p| format!("L{}R", p))
{
x1_filled = true;
Some(p)
} else {
None
}
} else if !x2_filled && px1 == x2 + x2_extra && px2 == x2 + x2_extra {
// We are at the right edge, try to fill the right side
if let Some(p) = fill_right3(w - x2 - x2_extra, py1, py2)
.map(|p| format!("R{}L", p))
{
x2_filled = true;
Some(p)
} else {
None
}
} else {
None
}
});
if x1_filled && x2_filled {
return Some(local_res);
}
}
}
}
return None;
}
// if y1 == 3 {
// return solve(h, w, h + 1 - y1, x1, h + 1 - y2, x2).map(flip_y);
// }
// assert!(y1 == 1 || y1 == 2);
if x1 != x2 {
fn combine_middle_part(
y1: usize,
x1: usize,
y2: usize,
x2: usize,
left: Option<(usize, String)>,
right: Option<(usize, String)>,
) -> Option<String> {
assert!(x1 < x2);
match (left, right) {
(Some((ly, lp)), Some((ry, rp))) => {
if x1 + 1 == x2 {
// They are next to each others, the y coordinates need to match, possibly after a flip
if ly == ry {
Some(format!("{}R{}", lp, rp))
} else if ly == 4 - ry && (y1 == 2 || y2 == 2) {
if y1 == 2 {
Some(format!("{}R{}", flip_x(lp), rp))
} else {
assert!(y2 == 2);
Some(format!("{}R{}", lp, flip_y(rp)))
}
} else {
None
}
} else {
// Not next to each others
if ly == 2 || ry == 2 {
None
} else {
let suffix = if ly == ry { "UUR" } else { "" };
let midwidth = if ly == ry { x2 - x1 - 2 } else { x2 - x1 - 1 };
if midwidth == 0 {
None
} else {
let midres = format!(
"{}D{}D{}{}",
"R".repeat(midwidth),
"L".repeat(midwidth - 1),
"R".repeat(midwidth),
suffix
);
let midres = if ly == 1 { midres } else { flip_y(midres) };
Some(format!("{}{}{}", lp, midres, rp))
}
}
}
}
_ => None,
}
}
// Solve both ends separately, then try to combine them in the middle
let left = fill_left(h, x1, y1);
let right = fill_left(h, w + 1 - x2, y2).map(|(y, p)| (y, flip_x(reverse(p))));
// println!("Left: {:?}", left);
// println!("Right: {:?}", right);
combine_middle_part(
y1,
x1,
y2,
x2,
fill_left(h, x1, y1),
fill_left(h, w + 1 - x2, y2).map(|(y, p)| (y, flip_x(reverse(p)))),
)
.or_else(|| {
if x1 == 1 && x2 >= 3 {
// Try to extend x1 one part to right
combine_middle_part(
y1,
x1 + 1,
y2,
x2,
solve(2, w, 1, y1, 2, 4 - y1).map(|p| (4 - y1, swap_xy(p))),
fill_left(h, w + 1 - x2, y2).map(|(y, p)| (y, flip_x(reverse(p)))),
)
} else {
None
}
})
// .or_else(|| if x1 == 1 && x2 == 2 {})
} else {
// The endpoints are in the same column
if y1 == 2 || y2 == 2 {
// One of the endpoints is on the center row
if w % 2 == 1 {
// No solutions with odd number of columns
return None;
}
let rev = y2 != 2;
let (y1, y2) = if rev { (y2, y1) } else { (y1, y2) };
let fy = y1 != 1;
let y1 = 1;
assert!(y1 == 1);
assert!(y2 == 2);
let res = if x1 % 2 == 1 {
if x1 == 1 {
// We are at the left wall, fill the right side
Some(format!("R{}LU", flip_x(fill_left(h, w - 1, 1).unwrap().1)))
} else {
// Flip the board and retry
solve(h, w, y1, w + 1 - x1, y2, w + 1 - x2).map(flip_x)
}
} else {
// Odd number of columns to the left, go there, then zigzag
if x1 == w {
Some(format!("L{}RU", fill_left(h, x1 - 1, 1).unwrap().1))
} else {
Some(format!(
"L{}RR{}L",
fill_left(h, x1 - 1, 1).unwrap().1,
flip_x(fill_left(h, w - x1, 3).unwrap().1)
))
}
};
let res = if fy { res.map(flip_y) } else { res };
if rev {
res.map(reverse)
} else {
res
}
} else {
let fy = y1 != 1;
let y1 = 1;
let y2 = 3;
let res = if w % 2 == 0 || x1 % 2 != 1 {
// Solutions exist only for cases where x divides the width into two even-width parts
None
} else {
let left = if x1 == 1 {
"D".to_string()
} else {
format!("L{}R", fill_left(h, x1 - 1, 1).unwrap().1)
};
let right = if x1 == w {
"D".to_string()
} else {
reverse(format!("R{}L", flip_x(fill_left(h, w - x1, 3).unwrap().1)))
};
Some(format!("{}{}", left, right))
};
if fy {
res.map(flip_y)
} else {
res
}
}
}
} else if h == 4 {
if (x1 + y1) % 2 == (x2 + y2) % 2 {
return None;
}
fn fill_left4(w: usize, y1: usize, y2: usize) -> Option<String> {
if y1 > y2 {
return fill_left4(w, 5 - y1, 5 - y2).map(flip_y);
}
if y1 == y2 {
return None;
}
assert!(y1 != y2);
assert!(w > 0);
if w == 1 {
if y1 == 1 && y2 == 4 {
Some("DDD".to_string())
} else if y1 == 4 && y2 == 1 {
Some("UUU".to_string())
} else {
None
}
} else {
let l = "L".repeat(w - 2);
let r = "R".repeat(w - 2);
if y1 == 1 {
if y2 == 2 {
Some(format!("L{}D{}D{}D{}RUU", l, r, l, r))
} else if y2 == 4 {
Some(format!("L{}D{}RDL{}D{}R", l, r, l, r))
} else {
None
}
} else if y1 == 2 {
if y2 == 3 {
Some(format!("UL{}D{}D{}D{}RU", l, r, l, r))
} else {
None
}
} else {
assert!(y1 == 3);
assert!(y2 == 4);
Some(format!("UUL{}D{}D{}D{}R", l, r, l, r))
}
}
}
fn fill_right4(w: usize, y1: usize, y2: usize) -> Option<String> {
fill_left4(w, y1, y2).map(flip_x)
}
if x2 - x1 <= 3 {
let x1_max_extra = (x1 - 1).min(2);
let x2_max_extra = (w - x2).min(2);
for x1_extra in 0..=x1_max_extra {
for x2_extra in 0..=x2_max_extra {
let local_res = brute_solve(
4,
x2 - x1 + 1 + x1_extra + x2_extra,
y1,
x1 + 1 - (x1 - x1_extra),
y2,
x2 + 1 - (x1 - x1_extra),
);
// println!("{:?}", local_res);
let mut x1_filled = x1 == 1;
let mut x2_filled = x2 == w;
if let Some(local_res) = local_res {
let mut x1_filled = x1 - x1_extra == 1;
let mut x2_filled = x2 + x2_extra == w;
let local_res = walk_and_modify(local_res, y1, x1, |py1, px1, py2, px2| {
if !x1_filled && px1 == x1 - x1_extra && px2 == x1 - x1_extra {
// We are at the left edge, try to fill the left side
if let Some(p) = fill_left4(x1 - 1 - x1_extra, py1, py2)
.map(|p| format!("L{}R", p))
{
x1_filled = true;
Some(p)
} else {
None
}
} else if !x2_filled && px1 == x2 + x2_extra && px2 == x2 + x2_extra {
// We are at the right edge, try to fill the right side
if let Some(p) = fill_right4(w - x2 - x2_extra, py1, py2)
.map(|p| format!("R{}L", p))
{
x2_filled = true;
Some(p)
} else {
None
}
} else {
None
}
});
if x1_filled && x2_filled {
return Some(local_res);
}
}
}
}
return None;
}
let (x1, left) = if x1 == 1 {
if y1 == 1 {
(1, (4, "DDD".to_string()))
} else if y1 == 2 {
(2, (4, "URDDLDR".to_string()))
} else if y1 == 3 {
(2, (1, "DRUULUR".to_string()))
} else {
(1, (1, "UUU".to_string()))
}
} else {
(
x1,
fill_left4(x1, y1, 1)
.map(|p| (1, p))
.or(fill_left4(x1, y1, 4).map(|p| (4, p)))
.unwrap(),
)
};
let (x2, right) = if x2 == w {
if y2 == 1 {
(w, (4, "UUU".to_string()))
} else if y2 == 2 {
(w - 1, (4, "RULUURD".to_string()))
} else if y2 == 3 {
(w - 1, (1, "RDLDDRU".to_string()))
} else {
(w, (1, "DDD".to_string()))
}
} else {
(
x2,
fill_right4(w + 1 - x2, y2, 1)
.map(reverse)
.map(|p| (1, p))
.or(fill_right4(w + 1 - x2, y2, 4).map(reverse).map(|p| (4, p)))
.unwrap(),
)
};
let mut res = left.1;
let mut y1 = left.0;
let mut x1 = x1;
while x1 + 1 < x2 {
if y1 == 1 {
res += "RDDD";
} else {
res += "RUUU";
}
y1 = 5 - y1;
x1 += 1;
}
assert!(y1 == right.0);
res += "R";
res += &right.1;
Some(res)
} else {
unimplemented!()
}
}
fn main() {
let stdin = std::io::stdin();
let stdin = stdin.lock();
let mut lines = stdin.lines();
let t: usize = lines.next().unwrap().unwrap().parse().unwrap();
for _ in 0..t {
let input: Vec<usize> = lines
.next()
.unwrap()
.unwrap()
.split_whitespace()
.map(|v| v.parse().unwrap())
.collect();
if let Some(res) = solve(input[0], input[1], input[2], input[3], input[4], input[5]) {
println!("YES");
println!("{}", res);
} else {
println!("NO");
}
}
}
#[cfg(test)]
mod tests {
use super::*;
fn assert_solution(h: usize, w: usize, y1: usize, x1: usize, y2: usize, x2: usize, path: &str) {
println!("{}", path);
let mut visited = vec![false; h * w];
let mut x = x1;
let mut y = y1;
visited[(x - 1) + (y - 1) * w] = true;
for c in path.chars() {
match c {
'U' => y -= 1,
'D' => y += 1,
'L' => x -= 1,
'R' => x += 1,
c => panic!("Invalid action '{}'", c),
}
assert!(
x >= 1 && x <= w && y >= 1 && y <= h,
"Solution {} walked out of bounds",
path
);
assert!(
!visited[(x - 1) + (y - 1) * w],
"Solution {} has already visited cell {}, {}",
path,
y,
x
);
visited[(x - 1) + (y - 1) * w] = true;
}
assert!(
visited.into_iter().all(std::convert::identity),
"Solution {} didn't visit all cells",
path
);
assert!((x, y) == (x2, y2));
}
fn assert_solvable(h: usize, w: usize, y1: usize, x1: usize, y2: usize, x2: usize) {
assert_solution(h, w, y1, x1, y2, x2, &solve(h, w, y1, x1, y2, x2).unwrap());
}
fn assert_solvable_perm(h: usize, w: usize, y1: usize, x1: usize, y2: usize, x2: usize) {
assert_solvable(h, w, y1, x1, y2, x2);
assert_solvable(h, w, y2, x2, y1, x1);
assert_solvable(w, h, x1, y1, x2, y2);
assert_solvable(w, h, x2, y2, x1, y1);
assert_solvable(h, w, h + 1 - y1, x1, h + 1 - y2, x2);
assert_solvable(h, w, h + 1 - y2, x2, h + 1 - y1, x1);
assert_solvable(w, h, w + 1 - x1, y1, w + 1 - x2, y2);
assert_solvable(w, h, w + 1 - x2, y2, w + 1 - x1, y1);
assert_solvable(h, w, y1, w + 1 - x1, y2, w + 1 - x2);
assert_solvable(h, w, y2, w + 1 - x2, y1, w + 1 - x1);
assert_solvable(w, h, x1, h + 1 - y1, x2, h + 1 - y2);
assert_solvable(w, h, x2, h + 1 - y2, x1, h + 1 - y1);
assert_solvable(h, w, h + 1 - y1, w + 1 - x1, h + 1 - y2, w + 1 - x2);
assert_solvable(h, w, h + 1 - y2, w + 1 - x2, h + 1 - y1, w + 1 - x1);
assert_solvable(w, h, w + 1 - x1, h + 1 - y1, w + 1 - x2, h + 1 - y2);
assert_solvable(w, h, w + 1 - x2, h + 1 - y2, w + 1 - x1, h + 1 - y1);
}
fn assert_unsolvable(h: usize, w: usize, y1: usize, x1: usize, y2: usize, x2: usize) {
assert!(solve(h, w, y1, x1, y2, x2).is_none());
}
fn assert_unsolvable_perm(h: usize, w: usize, y1: usize, x1: usize, y2: usize, x2: usize) {
assert_unsolvable(h, w, y1, x1, y2, x2);
assert_unsolvable(h, w, y2, x2, y1, x1);
assert_unsolvable(w, h, x1, y1, x2, y2);
assert_unsolvable(w, h, x2, y2, x1, y1);
assert_unsolvable(h, w, h + 1 - y1, x1, h + 1 - y2, x2);
assert_unsolvable(h, w, h + 1 - y2, x2, h + 1 - y1, x1);
assert_unsolvable(w, h, w + 1 - x1, y1, w + 1 - x2, y2);
assert_unsolvable(w, h, w + 1 - x2, y2, w + 1 - x1, y1);
assert_unsolvable(h, w, y1, w + 1 - x1, y2, w + 1 - x2);
assert_unsolvable(h, w, y2, w + 1 - x2, y1, w + 1 - x1);
assert_unsolvable(w, h, x1, h + 1 - y1, x2, h + 1 - y2);
assert_unsolvable(w, h, x2, h + 1 - y2, x1, h + 1 - y1);
assert_unsolvable(h, w, h + 1 - y1, w + 1 - x1, h + 1 - y2, w + 1 - x2);
assert_unsolvable(h, w, h + 1 - y2, w + 1 - x2, h + 1 - y1, w + 1 - x1);
assert_unsolvable(w, h, w + 1 - x1, h + 1 - y1, w + 1 - x2, h + 1 - y2);
assert_unsolvable(w, h, w + 1 - x2, h + 1 - y2, w + 1 - x1, h + 1 - y1);
}
#[test]
fn test_solve1() {
assert_solvable(1, 3, 1, 1, 1, 3);
assert_solvable(1, 3, 1, 3, 1, 1);
assert_unsolvable(1, 3, 1, 2, 1, 3);
}
#[test]
fn test_solve2() {
assert_unsolvable(2, 2, 1, 1, 2, 2);
assert_solvable(2, 2, 1, 1, 2, 1);
assert_solvable(2, 3, 1, 1, 2, 3);
assert_unsolvable(2, 3, 1, 1, 1, 3);
}
#[test]
fn foo() {
assert_solvable(4, 5, 1, 1, 2, 5);
panic!()
// assert_solvable(3,20, 1, 1, 2, 1);
// assert_solvable_perm(3, 3, 1, 1, 2, 2);
}
#[test]
fn test_solve3() {
assert_solvable(3, 3, 1, 1, 3, 3);
assert_solvable(3, 4, 1, 2, 1, 3);
assert_solvable(3, 4, 1, 2, 3, 3);
assert_unsolvable(3, 3, 1, 2, 1, 3);
// Width 1
assert_solvable_perm(3, 1, 1, 1, 3, 1);
assert_solvable_perm(3, 1, 3, 1, 1, 1);
assert_unsolvable_perm(3, 1, 1, 1, 2, 1);
assert_unsolvable_perm(3, 1, 3, 1, 2, 1);
assert_unsolvable_perm(3, 1, 2, 1, 1, 1);
assert_unsolvable_perm(3, 1, 2, 1, 3, 1);
// Width 2
assert_solvable_perm(3, 2, 1, 1, 1, 2);
assert_solvable_perm(3, 2, 1, 1, 2, 1);
assert_solvable_perm(3, 2, 1, 1, 3, 2);
assert_unsolvable_perm(3, 2, 1, 1, 2, 2);
assert_unsolvable_perm(3, 2, 1, 1, 3, 1);
// Width 3
assert_solvable_perm(3, 3, 1, 1, 2, 2);
assert_solvable_perm(3, 3, 1, 1, 3, 3);
assert_solvable_perm(3, 3, 1, 1, 3, 1);
assert_solvable_perm(3, 3, 1, 1, 1, 3);
for y in 1..=3 {
for x in 1..=3 {
if x != 2 || y != 1 {
assert_unsolvable_perm(3, 3, 1, 2, y, x);
}
}
}
// assert_solvable(3, 2, 3, 1, 1, 1);
// Wider
for x in 1..=6 {
assert_solvable(3, 6, 1, x, 2, x);
assert_solvable(3, 6, 2, x, 1, x);
assert_solvable(3, 6, 2, x, 3, x);
assert_solvable(3, 6, 3, x, 2, x);
}
for x in 1..=7 {
if x % 2 == 1 {
assert_solvable(3, 7, 1, x, 3, x);
assert_solvable(3, 7, 3, x, 1, x);
} else {
assert_unsolvable(3, 7, 1, x, 3, x);
assert_unsolvable(3, 7, 3, x, 1, x);
}
}
// Other manual samples
assert_solvable(3, 6, 3, 2, 3, 3);
assert_solvable(3, 6, 1, 2, 1, 3);
assert_unsolvable(3, 6, 1, 2, 1, 4);
assert_unsolvable(3, 6, 1, 2, 1, 5);
assert_unsolvable(3, 6, 1, 2, 1, 6);
assert_solvable(3, 6, 1, 3, 1, 4);
assert_unsolvable(3, 6, 1, 3, 1, 5);
assert_solvable(3, 6, 1, 3, 1, 6);
assert_solvable(3, 6, 1, 4, 1, 5);
assert_unsolvable(3, 6, 1, 4, 1, 6);
assert_solvable(3, 6, 1, 5, 1, 6);
}
#[test]
fn test_solve4() {
assert_solvable(4, 4, 1, 1, 1, 2);
}
#[test]
fn test_against_brute() {
for w in 1..=6 {
for h in 4..=4 {
for x1 in 1..=w {
for y1 in 1..=h {
for x2 in 1..=w {
for y2 in 1..=h {
if x1 != x2 || y1 != y2 {
println!("Testing {:?}", (h, w, y1, x1, y2, x2));
let br = brute_solve(h, w, y1, x1, y2, x2);
let sr = solve(h, w, y1, x1, y2, x2);
if br.is_some() {
assert!(sr.is_some(), "Brute found solution for instance {:?}, but solve didn't", (h, w, y1, x1, y2, x2));
assert_solution(h, w, y1, x1, y2, x2, &sr.unwrap());
assert_solution(h, w, y1, x1, y2, x2, &br.unwrap());
} else {
assert!(sr.is_none(), "Brute didn't find a solution for instance {:?}, but solve did with {}", (h, w, y1, x1, y2, x2), sr.unwrap());
}
}
}
}
}
}
}
}
}
}
Test details
Test 1
Group: 1, 5
Verdict: ACCEPTED
| input |
|---|
| 100 1 45 1 45 1 1 1 18 1 1 1 10 1 47 1 17 1 30 1 33 1 28 1 20 ... |
| correct output |
|---|
| YES LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL... |
| user output |
|---|
| YES LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL... Truncated |
Test 2
Group: 2, 5
Verdict: ACCEPTED
| input |
|---|
| 100 2 43 1 33 1 21 2 2 1 1 2 2 2 32 1 1 2 8 2 14 1 12 1 14 ... |
| correct output |
|---|
| NO NO NO NO YES ... |
| user output |
|---|
| NO NO NO NO YES ... Truncated |
Test 3
Group: 3, 5
Verdict: ACCEPTED
| input |
|---|
| 100 3 4 2 1 2 4 3 38 2 24 1 22 3 29 2 23 2 3 3 8 3 1 1 2 ... |
| correct output |
|---|
| NO NO NO YES RRRRRRRUULDLULDLULDLLUR ... |
| user output |
|---|
| NO NO NO YES RRRRRRRUULDLULDLULDLLUR ... Truncated |
Test 4
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 100 4 25 2 19 1 5 4 13 3 10 4 12 4 7 3 1 4 2 4 23 1 19 2 5 ... |
| correct output |
|---|
| YES DDRRRRRRULLLLLURRRRRULLLLLLLDD... |
| user output |
|---|
| YES DDRRRRRRULLLLLURRRRRULLLLLLLDD... Truncated |
Test 5
Group: 5
Verdict: RUNTIME ERROR
| input |
|---|
| 100 16 8 13 1 14 8 41 21 19 11 32 12 46 17 13 7 6 11 8 41 4 32 4 12 ... |
| correct output |
|---|
| NO YES LURULURULURULURULURRDDDDDDDDDR... |
| user output |
|---|
| (empty) |
Error:
thread 'main' panicked at 'not implemented', input/code.rs:669:9 note: run with `RUST_BACK...
Test 6
Group: 5
Verdict: RUNTIME ERROR
| input |
|---|
| 100 31 38 18 35 31 37 35 48 7 13 21 21 46 21 25 2 4 19 35 2 13 2 35 1 ... |
| correct output |
|---|
| YES LLLLLLLLLLLLDRRRRRRRRRRRRDLLLL... |
| user output |
|---|
| (empty) |
Error:
thread 'main' panicked at 'not implemented', input/code.rs:669:9 note: run with `RUST_BACK...
Test 7
Group: 2, 5
Verdict: ACCEPTED
| input |
|---|
| 100 2 4 1 3 1 4 2 4 2 2 1 1 2 4 2 3 1 2 2 4 2 3 1 4 ... |
| correct output |
|---|
| YES LLDRRRU NO NO NO ... |
| user output |
|---|
| YES LLDRRRU NO NO NO ... Truncated |
Test 8
Group: 2, 5
Verdict: ACCEPTED
| input |
|---|
| 100 2 5 1 2 2 4 2 5 1 2 1 1 2 5 2 1 1 2 2 5 1 1 1 5 ... |
| correct output |
|---|
| YES LDRRURRDL YES RRRDLLLLU NO ... |
| user output |
|---|
| YES LDRRURRDL YES RRRDLLLLU NO ... Truncated |
Test 9
Group: 3, 5
Verdict: ACCEPTED
| input |
|---|
| 100 3 4 1 1 2 3 3 4 2 4 3 2 3 4 2 1 3 1 3 4 1 4 3 4 ... |
| correct output |
|---|
| YES DDRRRUULLDR NO YES URRRDDLULDL ... |
| user output |
|---|
| YES RRRDDLLLURR NO YES URRRDDLULDL ... Truncated |
Test 10
Group: 3, 5
Verdict: ACCEPTED
| input |
|---|
| 100 3 5 3 4 3 2 3 5 3 5 2 3 3 5 3 1 2 2 3 5 3 1 3 2 ... |
| correct output |
|---|
| NO NO YES UURRRRDDLULDLU NO ... |
| user output |
|---|
| NO NO YES RRRRUULDLULLDR NO ... Truncated |
Test 11
Group: 3, 5
Verdict: ACCEPTED
| input |
|---|
| 100 3 8 2 8 1 2 3 8 2 4 1 7 3 8 3 4 2 7 3 8 2 5 3 1 ... |
| correct output |
|---|
| NO NO NO YES LLLDRRRRURDRUULLLLLLLDD ... |
| user output |
|---|
| NO NO NO YES DRURDRUULLLLLDRDLLUULDD ... Truncated |
Test 12
Group: 3, 5
Verdict: ACCEPTED
| input |
|---|
| 100 3 9 1 3 2 9 3 9 1 6 1 5 3 9 3 6 2 8 3 9 3 2 3 4 ... |
| correct output |
|---|
| NO NO NO NO NO ... |
| user output |
|---|
| NO NO NO NO NO ... Truncated |
Test 13
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 100 4 4 2 2 1 4 4 4 4 1 2 2 4 4 2 1 4 3 4 4 3 1 3 3 ... |
| correct output |
|---|
| YES DDLUUURRDDDRUUU YES UUURRRDLDRDLLUU NO ... |
| user output |
|---|
| YES RRDDLULDLUUURRR YES RRRUUULDDLLUURD NO ... Truncated |
Test 14
Group: 5
Verdict: RUNTIME ERROR
| input |
|---|
| 100 12 27 6 22 1 8 6 25 3 2 4 4 6 16 4 6 5 2 36 33 8 6 1 6 ... |
| correct output |
|---|
| YES DLDDDDDRUUUURDDDDRUURDDRRULURU... |
| user output |
|---|
| (empty) |
Error:
thread 'main' panicked at 'not implemented', input/code.rs:669:9 note: run with `RUST_BACK...
Test 15
Group: 3, 5
Verdict: ACCEPTED
| input |
|---|
| 100 3 12 3 5 1 4 3 20 3 19 2 19 3 34 3 9 2 9 3 38 2 15 3 15 ... |
| correct output |
|---|
| YES RRRRRRRUULDLULDLULDLULDLDLULDL... |
| user output |
|---|
| YES RRRRRRRUULDLULDLULDLULDLDLLLUU... Truncated |
Test 16
Group: 5
Verdict: RUNTIME ERROR
| input |
|---|
| 100 50 50 29 1 16 21 50 50 37 5 23 48 50 50 32 22 45 24 50 50 6 28 12 37 ... |
| correct output |
|---|
| YES DDDDDDDDDDDDDDDDDDDDDRUUUUUUUU... |
| user output |
|---|
| (empty) |
Error:
thread 'main' panicked at 'not implemented', input/code.rs:669:9 note: run with `RUST_BACK...