#353785 (Rust) No.675 ドットちゃんたち

• 問題: No.675 ドットちゃんたち
• ユーザー: wesrivery
• 提出日時: 2019-06-25 01:10:55
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 284 ms / 2,000 ms
• コード長: 6,531 bytes
• コンパイル時間: 14,076 ms
• コンパイル使用メモリ: 378,220 KB
• 実行使用メモリ: 44,160 KB
• 最終ジャッジ日時: 2024-06-22 23:33:24
• 合計ジャッジ時間: 18,168 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	275 ms; 44,032 KB
testcase_06	AC	282 ms; 44,160 KB
testcase_07	AC	254 ms; 39,808 KB
testcase_08	AC	275 ms; 44,032 KB
testcase_09	AC	284 ms; 44,160 KB
testcase_10	AC	278 ms; 44,032 KB
testcase_11	AC	274 ms; 44,032 KB

ソースコード

use std::ops::Mul;
use std::ops::Add;
use std::ops::Index;
use std::iter::Sum;
use std::fmt::{Debug, Result, Formatter, Display};

#[derive(Eq, Clone)]
struct Mat<T: PartialEq + Eq + Debug + Display> {
    inside_vec: Vec<Vec<T>>,
    pub row: usize,
    pub col: usize,
}

impl<T: PartialEq + Eq + Debug + Display> Index<usize> for Mat<T> {
    type Output = Vec<T>;

    fn index(&self, i: usize) -> &Self::Output {
        &self.inside_vec[i]
    }
}

impl<T: PartialEq + Eq + Debug + Display> Mat<T> {

    pub fn new(v: Vec<Vec<T>>) -> Self {
        if let Some((row, col)) = Mat::row_col(&v) {
            Mat { inside_vec: v,
                  row: row,
                  col: col }
        } else {
            panic!("passed vector's length is not valid.");
        }
    }

    pub fn from_vec(v: Vec<T>) -> Self {
        let col = v.len();
        Mat { inside_vec: vec![v],
              row: 1,
              col: col }
    }

    fn row_col(v: &Vec<Vec<T>>) -> Option<(usize, usize)> {
        let col = v[0].len();
        for line in v.iter() {
            if line.len() != col {
                return None;
            }
        }
        return Some((v.len(), col));
    }
}

impl<T: Copy + PartialEq + Eq + Debug + Display> Mat<T> {
    pub fn transpose(self) -> Self {
        let row = self.col;
        let col = self.row;
        let mut inside: Vec<Vec<T>> = Vec::with_capacity(row);
        for i in 0..row {
            let cols = (0..col).map(|k| self[k][i]);
            inside.push(cols.collect());
        }

        Mat { inside_vec: inside,
              row: row,
              col: col }
    }
}

impl<T: PartialEq + Eq + Debug + Display> PartialEq for Mat<T> {
    fn eq(&self, other: &Self) -> bool {
        if self.row == other.row && self.col == other.col {
            for row in 0..self.row {
                for col in 0..self.col {
                    if self[row][col] != other[row][col] {
                        return false;
                    }
                }
            }
            return true;
        }

        return false;
    }
}

impl<T: PartialEq + Eq + Debug + Display> Debug for Mat<T> {
    fn fmt(&self, f: &mut Formatter) -> Result {
        let mut s = "".to_string();
        for line in &self.inside_vec {
            s += "|";
            for val in line {
                s += &format!(" {:^3}", val);
            }
            s += " |\n";
        }
        write!(f, "{}", s)
    }
}

impl<T: PartialEq + Eq + Debug + Display> Display for Mat<T> {
    fn fmt(&self, f: &mut Formatter) -> Result {
        let mut s = "".to_string();
        for line in &self.inside_vec {
            s += "|";
            for val in line {
                s += &format!(" {:^3}", val);
            }
            s += " |\n";
        }
        write!(f, "{}", s)
    }
}

impl<T> Mul for Mat<T>
    where T: Mul<Output = T> + Add + Sum + Copy + PartialEq + Eq + Debug + Display {

    type Output = Self;

    fn mul(self, rhs: Self) -> Self {

        if self.col != rhs.row {
            panic!("length of column of left hand side doesn't equal to length of row of right hand side.");
        }

        let mut product: Vec<Vec<T>> = Vec::with_capacity(rhs.row);
        for _ in 0..rhs.row {
            product.push(Vec::<T>::with_capacity(self.col));
        }

        for i in 0..self.row {
            for j in 0..rhs.col {
                let row = self[i].iter();
                let col = (0..rhs.row).map(|k| rhs[k][j]);
                product[i].push(row.zip(col).map(|(s, r)| *s * r).sum());
            }
        }

        Mat::new(product)
    }
}

impl<T> Add for Mat<T>
  where T: Add<Output = T> + Copy + PartialEq + Eq + Debug + Display {

    type Output = Self;

    fn add(self, rhs: Self) -> Self {
        if self.row != rhs.row {
            panic!("length of row is not currespond.");
        }
        if self.col != rhs.col {
            panic!("length of column is not currespond.");
        }

        let mut sum: Vec<Vec<T>> = Vec::with_capacity(self.row);
        for _ in 0..self.row {
            sum.push(Vec::<T>::with_capacity(self.col));
        }

        for i in 0..self.row {
            for j in 0..self.col {
                sum[i].push(self[i][j] + rhs[i][j]);
            }
        }
        Mat::new(sum)
    }
}

#[allow(unused_macros)]
macro_rules! invec {
    ( $t:ty ) => {{
        let mut s = String::new();
        match std::io::stdin().read_line(&mut s) {
            Ok(0) => Vec::<$t>::new(),
            Ok(_) => s.trim().split_whitespace().map(|s| s.parse::<$t>().unwrap()).collect::<Vec<$t>>(),
            Err(_) => Vec::<$t>::new(),
        }
    }}
}

#[allow(unused_macros)]
macro_rules! input {
    ( $($t:ty),* ) => {{
        let mut s = String::new();
        std::io::stdin().read_line(&mut s);
        let mut splits = s.trim().split_whitespace();
        ($(
            {
                 splits.next().unwrap().parse::<$t>().unwrap()
            },
        )*)
    }}
}

fn input_command() -> Mat<i64> {
    let commands = invec!(i64);
    let rotation = vec![vec![0, 1, 0],
                        vec![-1, 0, 0],
                        vec![0, 0, 1]];

    if commands.len() > 1 {
        let command = commands[0];
        let pos = commands[1];
        match command {
            1 => Mat::new(vec![vec![1, 0, pos],
                               vec![0, 1, 0],
                               vec![0, 0, 1]]),
            2 => Mat::new(vec![vec![1, 0, 0],
                               vec![0, 1, pos],
                               vec![0, 0, 1]]),
            _ => panic!(""),
        }
    } else {
        Mat::new(rotation)
    }
}

#[allow(unused_must_use)]
#[allow(unused_variables)]
fn solve() {
    let (n, px, py) = input!(usize, i64, i64);

    let mut commands = Vec::<Mat<i64>>::with_capacity(n);

    for i in 0..n {
        commands.push(input_command());
    }

    let mut multi_mats = Vec::<Mat<i64>>::with_capacity(n);

    let mut current_mat = Mat::new(vec![vec![1, 0, 0],
                                        vec![0, 1, 0],
                                        vec![0, 0, 1]]);

    for command in commands.iter().rev() {
        let mat = current_mat.clone() * command.clone();
        multi_mats.push(mat.clone());
        current_mat = mat;
    }

    multi_mats.reverse();
    for mat in multi_mats {
        let v = mat * Mat::from_vec(vec![px, py, 1]).transpose();
        println!("{} {}", v[0][0], v[1][0]);
    }
}

fn main() {
    solve();
}