#528499 (Rust) No.1167 Graduation Trip

提出ソース

結果

問題	No.1167 Graduation Trip
ユーザー	akakimidori
提出日時	2020-08-12 07:13:12
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	122 ms / 4,000 ms
コード長	9,868 bytes
コンパイル時間	15,904 ms
コンパイル使用メモリ	406,960 KB
実行使用メモリ	13,056 KB
最終ジャッジ日時	2024-10-09 16:51:56
合計ジャッジ時間	20,755 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	98 ms 8,064 KB
testcase_01	AC	82 ms 8,064 KB
testcase_02	AC	69 ms 8,064 KB
testcase_03	AC	97 ms 8,064 KB
testcase_04	AC	98 ms 8,064 KB
testcase_05	AC	85 ms 8,064 KB
testcase_06	AC	98 ms 8,064 KB
testcase_07	AC	81 ms 8,192 KB
testcase_08	AC	71 ms 8,064 KB
testcase_09	AC	90 ms 8,192 KB
testcase_10	AC	120 ms 13,056 KB
testcase_11	AC	122 ms 12,672 KB
testcase_12	AC	120 ms 13,056 KB
testcase_13	AC	120 ms 12,800 KB
testcase_14	AC	120 ms 12,928 KB
testcase_15	AC	106 ms 13,056 KB
testcase_16	AC	91 ms 12,800 KB
testcase_17	AC	119 ms 12,928 KB
testcase_18	AC	115 ms 12,928 KB
testcase_19	AC	122 ms 13,056 KB
testcase_20	AC	5 ms 6,820 KB
testcase_21	AC	7 ms 6,816 KB
testcase_22	AC	5 ms 6,816 KB
testcase_23	AC	7 ms 6,816 KB
testcase_24	AC	7 ms 6,816 KB
testcase_25	AC	5 ms 6,820 KB
testcase_26	AC	5 ms 6,820 KB
testcase_27	AC	6 ms 6,816 KB
testcase_28	AC	7 ms 6,820 KB
testcase_29	AC	5 ms 6,820 KB
testcase_30	AC	33 ms 12,672 KB
testcase_31	AC	44 ms 12,928 KB
testcase_32	AC	44 ms 12,800 KB
testcase_33	AC	2 ms 6,820 KB
testcase_34	AC	2 ms 6,816 KB
testcase_35	AC	1 ms 6,816 KB
testcase_36	AC	1 ms 6,816 KB
testcase_37	AC	1 ms 6,820 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// ---------- begin ModInt ----------
mod modint {

    #[allow(dead_code)]
    pub struct Mod;
    impl ConstantModulo for Mod {
        const MOD: u32 = 1_000_000_007;
    }

    #[allow(dead_code)]
    pub struct StaticMod;
    static mut STATIC_MOD: u32 = 0;
    impl Modulo for StaticMod {
        fn modulo() -> u32 {
            unsafe { STATIC_MOD }
        }
    }

    #[allow(dead_code)]
    impl StaticMod {
        pub fn set_modulo(p: u32) {
            unsafe {
                STATIC_MOD = p;
            }
        }
    }

    use std::marker::*;
    use std::ops::*;

    pub trait Modulo {
        fn modulo() -> u32;
    }

    pub trait ConstantModulo {
        const MOD: u32;
    }

    impl<T> Modulo for T
    where
        T: ConstantModulo,
    {
        fn modulo() -> u32 {
            T::MOD
        }
    }

    pub struct ModInt<T>(pub u32, PhantomData<T>);

    impl<T> Clone for ModInt<T> {
        fn clone(&self) -> Self {
            ModInt::new_unchecked(self.0)
        }
    }

    impl<T> Copy for ModInt<T> {}

    impl<T: Modulo> Add for ModInt<T> {
        type Output = ModInt<T>;
        fn add(self, rhs: Self) -> Self::Output {
            let mut d = self.0 + rhs.0;
            if d >= T::modulo() {
                d -= T::modulo();
            }
            ModInt::new_unchecked(d)
        }
    }

    impl<T: Modulo> AddAssign for ModInt<T> {
        fn add_assign(&mut self, rhs: Self) {
            *self = *self + rhs;
        }
    }

    impl<T: Modulo> Sub for ModInt<T> {
        type Output = ModInt<T>;
        fn sub(self, rhs: Self) -> Self::Output {
            let mut d = T::modulo() + self.0 - rhs.0;
            if d >= T::modulo() {
                d -= T::modulo();
            }
            ModInt::new_unchecked(d)
        }
    }

    impl<T: Modulo> SubAssign for ModInt<T> {
        fn sub_assign(&mut self, rhs: Self) {
            *self = *self - rhs;
        }
    }

    impl<T: Modulo> Mul for ModInt<T> {
        type Output = ModInt<T>;
        fn mul(self, rhs: Self) -> Self::Output {
            let v = self.0 as u64 * rhs.0 as u64 % T::modulo() as u64;
            ModInt::new_unchecked(v as u32)
        }
    }

    impl<T: Modulo> MulAssign for ModInt<T> {
        fn mul_assign(&mut self, rhs: Self) {
            *self = *self * rhs;
        }
    }

    impl<T: Modulo> Neg for ModInt<T> {
        type Output = ModInt<T>;
        fn neg(self) -> Self::Output {
            if self.0 == 0 {
                Self::zero()
            } else {
                Self::new_unchecked(T::modulo() - self.0)
            }
        }
    }

    impl<T> std::fmt::Display for ModInt<T> {
        fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
            write!(f, "{}", self.0)
        }
    }

    impl<T: Modulo> std::str::FromStr for ModInt<T> {
        type Err = std::num::ParseIntError;
        fn from_str(s: &str) -> Result<Self, Self::Err> {
            let val = s.parse::<u32>()?;
            Ok(ModInt::new(val))
        }
    }

    impl<T: Modulo> From<usize> for ModInt<T> {
        fn from(val: usize) -> ModInt<T> {
            ModInt::new_unchecked((val % T::modulo() as usize) as u32)
        }
    }

    impl<T: Modulo> From<u64> for ModInt<T> {
        fn from(val: u64) -> ModInt<T> {
            ModInt::new_unchecked((val % T::modulo() as u64) as u32)
        }
    }

    impl<T: Modulo> From<i64> for ModInt<T> {
        fn from(val: i64) -> ModInt<T> {
            let m = T::modulo() as i64;
            ModInt::new((val % m + m) as u32)
        }
    }

    #[allow(dead_code)]
    impl<T> ModInt<T> {
        pub fn new_unchecked(d: u32) -> Self {
            ModInt(d, PhantomData)
        }
        pub fn zero() -> Self {
            ModInt::new_unchecked(0)
        }
        pub fn one() -> Self {
            ModInt::new_unchecked(1)
        }
        pub fn is_zero(&self) -> bool {
            self.0 == 0
        }
    }

    #[allow(dead_code)]
    impl<T: Modulo> ModInt<T> {
        pub fn new(d: u32) -> Self {
            ModInt::new_unchecked(d % T::modulo())
        }
        pub fn pow(&self, mut n: u64) -> Self {
            let mut t = Self::one();
            let mut s = *self;
            while n > 0 {
                if n & 1 == 1 {
                    t *= s;
                }
                s *= s;
                n >>= 1;
            }
            t
        }
        pub fn inv(&self) -> Self {
            assert!(self.0 != 0);
            self.pow(T::modulo() as u64 - 2)
        }
    }

    #[allow(dead_code)]
    pub fn mod_pow(r: u64, mut n: u64, m: u64) -> u64 {
        let mut t = 1 % m;
        let mut s = r % m;
        while n > 0 {
            if n & 1 == 1 {
                t = t * s % m;
            }
            s = s * s % m;
            n >>= 1;
        }
        t
    }
}
// ---------- end ModInt ----------

pub trait MoOperator {
    type Value;
    type Query;
    type Answer;
    fn init(&mut self);
    fn insert(&mut self, v: &Self::Value);
    fn snap(&mut self);
    fn rollback(&mut self);
    fn answer(&mut self, q: Self::Query) -> Self::Answer;
    fn solve(
        &mut self,
        array: &[Self::Value],
        mut query: Vec<(usize, usize, Self::Query)>,
        answer: &mut [Self::Answer],
    ) {
        let state = self;
        let size = array.len();
        assert!(query.len() <= answer.len());
        assert!(query.iter().all(|p| p.0 < p.1 && p.1 <= size));
        if query.is_empty() {
            return;
        }
        let batch = (size as f64 / (query.len() as f64).sqrt()).ceil() as usize;
        let mut q = vec![];
        std::mem::swap(&mut q, &mut query);
        state.init();
        state.snap();
        let mut query = (0..(size / batch + 1)).map(|_| vec![]).collect::<Vec<_>>();
        for (i, (l, r, op)) in q.into_iter().enumerate() {
            if r - l <= batch {
                for i in l..r {
                    state.insert(&array[i]);
                }
                answer[i] = state.answer(op);
                state.rollback();
            } else {
                query[l / batch].push((r, l, i, op));
            }
        }
        for (i, mut query) in query.into_iter().enumerate() {
            state.init();
            query.sort_unstable_by_key(|p| p.0);
            let mid = (i + 1) * batch;
            let mut t = mid;
            for (r, l, k, op) in query.into_iter() {
                while t < r {
                    state.insert(&array[t]);
                    t += 1;
                }
                state.snap();
                let mut x = mid;
                while x > l {
                    x -= 1;
                    state.insert(&array[x]);
                }
                answer[k] = state.answer(op);
                state.rollback();
            }
        }
    }
}
// ---------- begin scannner ----------
#[allow(dead_code)]
mod scanner {
    use std::str::FromStr;
    use std::str::SplitWhitespace;
    use std::io::Read;
    use std;
    pub struct Scanner<'a> {
        it: SplitWhitespace<'a>
    }
    impl<'a> Scanner<'a> {
        pub fn new(s: &'a String) -> Scanner<'a> {
            Scanner {
                it: s.split_whitespace()
            }
        }
        pub fn next<T: FromStr>(&mut self) -> T {
            match self.it.next().unwrap().parse::<T>() {
                Ok(v) => v,
                _ => panic!("Scanner error")
            }
        }
        pub fn next_chars(&mut self) -> Vec<char> {
            self.next::<String>().chars().collect()
        }
        pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
            (0..len).map(|_| self.next()).collect()
        }
    }
    pub fn read_string() -> String {
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }
}
// ---------- end scannner ----------

use std::io::Write;
use modint::*;

type M = ModInt<Mod>;

fn main() {
    let sc = scanner::read_string();
    let mut sc = scanner::Scanner::new(&sc);
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    run(&mut sc, &mut out);
}

struct State {
    base: Vec<usize>,
    save: Vec<usize>,
}

impl MoOperator for State {
    type Value = usize;
    type Query = ();
    type Answer = usize;
    fn init(&mut self) {
        self.base.clear();
        self.save.clear();
    }
    fn insert(&mut self, v: &Self::Value) {
        let mut x = *v;
        for b in self.base.iter() {
            x = std::cmp::min(x, *b ^ x);
        }
        if x > 0 {
            self.base.push(x);
        }
    }
    fn snap(&mut self) {
        self.save = self.base.clone();
    }
    fn rollback(&mut self) {
        self.base = self.save.clone();
    }
    fn answer(&mut self, _q: Self::Query) -> Self::Answer {
        self.base.len()
    }
}

fn run(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<std::io::StdoutLock>) {
    let n: usize = sc.next();
    let q: usize = sc.next();
    let a: Vec<usize> = sc.next_vec(n);
    let mut ask = vec![vec![]; q];
    let mut query = vec![];
    for q in ask.iter_mut() {
        let m: usize = sc.next();
        let mut l = 0;
        for _ in 0..m {
            let k: usize = sc.next();
            q.push((l, k, ()));
            l = k;
        }
        q.push((l, n, ()));
        for q in q.iter() {
            query.push(*q);
        }
    }
    let mut res = vec![0; query.len()];
    State {
        base: vec![],
        save: vec![],
    }.solve(&a, query, &mut res);
    let mut s = 0;
    for ask in ask.iter() {
        let mut ans = M::one();
        for (res, &(l, r, _)) in res[s..].iter().zip(ask.iter()) {
            ans *= M::new(2).pow((r - l - *res) as u64);
        }
        s += ask.len();
        writeln!(out, "{}", ans).ok();
    }
}

yukicoder

結果

テストケース

ソースコード