結果

問題 No.675 ドットちゃんたち
ユーザー wesriverywesrivery
提出日時 2019-06-26 03:19:53
言語 Rust
(1.77.0)
結果
AC  
実行時間 268 ms / 2,000 ms
コード長 7,321 bytes
コンパイル時間 2,325 ms
コンパイル使用メモリ 161,684 KB
実行使用メモリ 44,072 KB
最終ジャッジ日時 2023-09-05 22:38:25
合計ジャッジ時間 5,046 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 248 ms
44,020 KB
testcase_06 AC 262 ms
44,044 KB
testcase_07 AC 235 ms
39,812 KB
testcase_08 AC 259 ms
44,024 KB
testcase_09 AC 268 ms
44,072 KB
testcase_10 AC 265 ms
44,020 KB
testcase_11 AC 260 ms
44,028 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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> Mul for &'_ Mat<T>
    where T: Mul<Output = T> + Add + Sum + Copy + PartialEq + Eq + Debug + Display {

    type Output = Mat<T>;

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

        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: 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 * &command;
        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();
}
0