#208414 (Rust) No.261 ぐるぐるぐるぐる！あみだくじ！

• 問題: No.261 ぐるぐるぐるぐる！あみだくじ！
• ユーザー: sntea
• 提出日時: 2017-10-08 15:00:19
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 292 ms / 5,000 ms
• コード長: 6,611 bytes
• コンパイル時間: 13,814 ms
• コンパイル使用メモリ: 378,264 KB
• 実行使用メモリ: 27,276 KB
• 最終ジャッジ日時: 2024-11-17 05:31:47
• 合計ジャッジ時間: 16,345 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	AC * 3
other	AC * 37

コンパイルメッセージ

warning: unused macro definition: `mvec`
  --> src/main.rs:39:14
   |
39 | macro_rules! mvec {
   |              ^^^^
   |
   = note: `#[warn(unused_macros)]` on by default

warning: unused macro definition: `debug`
  --> src/main.rs:48:14
   |
48 | macro_rules! debug {
   |              ^^^^^

warning: function `printiter` is never used
  --> src/main.rs:54:4
   |
54 | fn printiter<'a, T>(v: &'a T)
   |    ^^^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

ソースコード

// use std::ops::{Index, IndexMut};
// use std::cmp::{Ordering, min, max};
// use std::collections::{BinaryHeap, BTreeMap};
// use std::collections::btree_map::Entry::{Occupied, Vacant};
// use std::clone::Clone;

fn getline() -> String{
    let mut res = String::new();
    std::io::stdin().read_line(&mut res).ok();
    res
}

macro_rules! readl {
    ($t: ty) => {
        {
            let s = getline();
            s.trim().parse::<$t>().unwrap()
        }
    };
    ($( $t: ty),+ ) => {
        {
            let s = getline();
            let mut iter = s.trim().split(' ');
            ($(iter.next().unwrap().parse::<$t>().unwrap(),)*) 
        }
    };
}

macro_rules! readlvec {
    ($t: ty) => {
        {
            let s = getline();
            let iter = s.trim().split(' ');
            iter.map(|x| x.parse().unwrap()).collect::<Vec<$t>>()
        }
    }
}

macro_rules! mvec {
    ($v: expr, $s: expr) => {
        vec![$v; $s]
    };
    ($v: expr, $s: expr, $($t: expr),*) => {
        vec![mvec!($v, $($t),*); $s]
    };
}

macro_rules! debug {
    ($x: expr) => {
        println!("{}: {:?}", stringify!($x), $x)
    }
}

fn printiter<'a, T>(v: &'a T)
where
    &'a T: std::iter::IntoIterator, 
    <&'a T as std::iter::IntoIterator>::Item: std::fmt::Display {
    for (i,e) in v.into_iter().enumerate() {
        if i != 0 {
            print!(" ");
        }
        print!("{}", e);
    }
    println!("");
}

mod algebra {
    use std::ops::{Add, Mul, Neg, Sub, Div};
    use std;

    pub trait Zero {
        fn zero(&self) -> Self;
    }
    
    pub trait Monoid: Add<Self, Output=Self>+Zero 
        where Self : std::marker::Sized{
    }

    pub trait Group: Monoid+Neg<Output=Self>+Sub<Self, Output=Self> {
    }

    pub trait Ring: Group+Mul<Self, Output=Self> {
    }

    pub trait One {
        fn one(&self) -> Self;
    }

    pub trait Field: Ring+One+Div<Self, Output=Self> {
    }
}

fn baby_step_giant_step<T>(x: T, r: T, ord: u64) -> Option<u64>
    where T: algebra::Group+std::clone::Clone+std::cmp::Ord {
    let mut res = None;
    let root = {
        let mut i = 0;
        while i*i <= ord {
            i += 1;
        }
        i+1
    };
    let mut baby_steps = Vec::with_capacity(root as usize);
    let mut giant_steps = Vec::with_capacity(root as usize);
    let mut giant_step = x.zero();
    let rinv = -r.clone();
    for _ in 0..root {
        giant_step = giant_step+rinv.clone();
    }
    let mut b = x.zero();
    let mut g = x;
    for i in 0..root {
        baby_steps.push(b.clone());
        giant_steps.push((g.clone(), i));
        g = g+giant_step.clone();
        b = b+r.clone();
    }
    giant_steps.sort();
    let baby_steps = baby_steps;
    let giant_steps = giant_steps;
    
    for i in 0..root {
        let check = |p: usize| {
            baby_steps[i as usize] <= giant_steps[p].0
        };
        let lower_bound = {
            if !check(root as usize-1) {
                None
            } else if check(0) {
                Some(0)
            } else {
                let mut l = 0;
                let mut r = root as usize-1;
                while l+1 < r {
                    let m = (l+r)/2;
                    if check(m) {
                        r = m;
                    } else {
                        l = m;
                    }
                }
                Some(r)
            }
        };
        match lower_bound {
            Some(p) if baby_steps[i as usize] == giant_steps[p].0 => {
                res = Some((root*giant_steps[p].1+i)%ord);
                break;
            },
            _ => {
            },
        }
    }
    res
}

#[derive(Clone, Debug)]
struct Replacement{
    v: Vec<usize>,
}

use std::cmp::*;

impl std::cmp::PartialEq for Replacement {
    fn eq(&self, other: &Replacement) -> bool {
        self.v == other.v
    }
}

impl Eq for Replacement {}

impl PartialOrd for Replacement {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        self.v.partial_cmp(&other.v)
    }
}

impl Ord for Replacement {
    fn cmp(&self, other: &Self) -> Ordering {
        self.v.cmp(&other.v)
    }
}

impl Replacement {
    fn dfs(&self, used: &mut Vec<bool>, p: usize) -> u64 {
        if used[p] {
            0
        } else {
            used[p] = true;
            self.dfs(used, self.v[p])+1
        }
    }
    
    fn get_ord(&self) -> u64 {
        let n = self.v.len();
        let mut used = vec![false; n];
        let mut res = 1;
        for i in 0..n {
            let ret = self.dfs(&mut used, i);
            if ret != 0 {
                res = lcm(res, ret);
            }
        }
        res
    }
}

impl std::ops::Add for Replacement {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        assert!(rhs.v.len() == self.v.len());
        let n = self.v.len();
        let mut res = vec![0; n];
        for i in 0..n {
            res[i] = self.v[rhs.v[i]];
        }
        Replacement {
            v: res
        }
    }
}

impl std::ops::Neg for Replacement {
    type Output = Self;

    fn neg(self) -> Replacement {
        let n = self.v.len();
        let mut res = vec![0;n];
        for i in 0..n {
            res[self.v[i]] = i;
        }
        Replacement{
            v: res
        }
    }
}

impl std::ops::Sub for Replacement {
    type Output = Self;

    fn sub(self, rhs: Replacement) -> Replacement {
        self+(-rhs)
    }
}

impl algebra::Zero for Replacement {
    fn zero(&self) -> Self {
        Replacement{
            v: (0..self.v.len()).collect(),
        }
    }
}

impl algebra::Monoid for Replacement {}
impl algebra::Group for Replacement {}

fn gcd(x: u64, y: u64) -> u64 {
    if y == 0 {
        x
    } else {
        gcd(y, x%y)
    }
}

fn lcm(x: u64, y: u64) -> u64 {
    x*y / gcd(x, y)
}

fn main() {
    let n = readl!(usize);
    let k = readl!(usize);
    let mut v: Vec<_> = (0..n).collect();
    for _ in 0..k {
        let (x, y) = readl!(usize, usize);
        v.swap(x-1, y-1);
    }
    let r = Replacement{v: v};
    // debug!(r.clone()-r.clone());
    let ord = r.get_ord();
    // debug!(ord);
    let q = readl!(usize);
    for _ in 0..q {
        let a = Replacement {
            v: readlvec!(usize).into_iter().map(|x| x-1).collect(),
        };
        let log = baby_step_giant_step(a, r.clone(), ord);
        if let Some(log) = log {
            if log == 0 {
                println!("{}", log+ord);
            } else {
                println!("{}", log);
            }
        } else {
            println!("-1");
        }
    }
    
}