Vaihdot

use std::collections::{HashMap, VecDeque};
use std::io::BufRead;

struct Solver {
    reachability: HashMap<Vec<usize>, (usize, usize)>,
}

const BRUTE_N: usize = 6;
impl Solver {
    fn new() -> Self {
        let mut reachability = HashMap::new();

        for n in 1..BRUTE_N {
            let mut q: VecDeque<Vec<usize>> = VecDeque::new();
            q.push_back((1..=n).collect());
            while let Some(s) = q.pop_front() {
                let mut s = s;
                for a in 0..n {
                    for b in a + 2..n {
                        s.swap(a, b);
                        if !reachability.contains_key(&s) {
                            reachability.insert(s.clone(), (a, b));
                            q.push_back(s.clone());
                        }
                        s.swap(a, b);
                    }
                }
            }
        }

        Self { reachability }
    }

    fn solve(&self, x: Vec<usize>) -> Option<Vec<(usize, usize)>> {
        if x.len() <= BRUTE_N {
            let target: Vec<usize> = (1..=x.len()).collect();
            if !self.reachability.contains_key(&x) && x != target {
                return None;
            }
            let mut res = Vec::new();
            let mut x = x;

            while x != target {
                let (a, b) = self.reachability.get(&x).unwrap();
                res.push((a + 1, b + 1));
                x.swap(*a, *b);
            }

            Some(res)
        } else {
            let mut res = Vec::new();
            let mut x = x;

            for i in 0..x.len() {
                let j = x.iter().position(|v| *v == i + 1).unwrap();
                let k = {
                    let mut k = 0;
                    while (i as isize - k as isize).abs() <= 1
                        || (j as isize - k as isize).abs() <= 1
                    {
                        k += 1;
                    }
                    k as usize
                };
                if i != j {
                    res.push((i + 1, k + 1));
                    res.push((j + 1, k + 1));
                    res.push((i + 1, k + 1));
                    x.swap(i, k);
                    x.swap(j, k);
                    x.swap(i, k);
                }
            }

            Some(res)
        }
    }
}

fn main() {
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let mut lines = stdin.lines();
    let solver = Solver::new();

    let t: usize = lines.next().unwrap().unwrap().parse().unwrap();
    for _ in 0..t {
        let _n: usize = lines.next().unwrap().unwrap().parse().unwrap();
        let x: Vec<usize> = lines
            .next()
            .unwrap()
            .unwrap()
            .split_whitespace()
            .map(|v| v.parse().unwrap())
            .collect();
        if let Some(res) = solver.solve(x) {
            println!("{}", res.len());
            for (a, b) in res {
                println!("{} {}", a, b);
            }
        } else {
            println!("-1");
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn assert_correct(x: Vec<usize>, res: Vec<(usize, usize)>) {
        assert!(res.len() <= 5 * x.len());
        let mut x = x;
        for (a, b) in res {
            x.swap(a - 1, b - 1);
        }
        let target: Vec<usize> = (1..=x.len()).collect();
        assert_eq!(x, target);
    }

    fn assert_some(x: Vec<usize>) {
        let solver = Solver::new();
        assert_correct(x.clone(), solver.solve(x).unwrap());
    }

    fn assert_none(x: Vec<usize>) {
        let solver = Solver::new();
        assert_eq!(solver.solve(x), None);
    }

    #[test]
    fn test_sample() {
        assert_some(vec![1, 2]);
        assert_some(vec![5, 4, 3, 2, 1]);
        assert_none(vec![2, 1, 3]);
        assert_some(vec![2, 4, 3, 1]);
    }

    #[test]
    fn test_large() {
        assert_some(vec![7, 5, 6, 4, 3, 1, 2]);
    }
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED