Submission #15420993


Source Code Expand

Copy
#[allow(unused_macros, dead_code)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros, dead_code)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros, dead_code)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(dead_code)]
struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<usize>,
    size: Vec<usize>,
}

#[allow(dead_code)]
impl UnionFind {
    fn new(n: usize) -> UnionFind {
        let mut p = vec![0; n];
        for i in 0..n {
            p[i] = i;
        }
        return UnionFind {
            parent: p,
            rank: vec![0; n],
            size: vec![1; n],
        };
    }

    fn find(&mut self, x: usize) -> usize {
        if x == self.parent[x] {
            x
        } else {
            let p = self.parent[x];
            let pr = self.find(p);
            self.parent[x] = pr;
            pr
        }
    }

    fn same(&mut self, a: usize, b: usize) -> bool {
        self.find(a) == self.find(b)
    }

    fn unite(&mut self, a: usize, b: usize) {
        let a_root = self.find(a);
        let b_root = self.find(b);
        if a_root == b_root {
            return;
        }
        if self.rank[a_root] > self.rank[b_root] {
            self.parent[b_root] = a_root;
            self.size[a_root] += self.size[b_root];
        } else {
            self.parent[a_root] = b_root;
            self.size[b_root] += self.size[a_root];
            if self.rank[a_root] == self.rank[b_root] {
                self.rank[b_root] += 1;
            }
        }
    }

    fn get_size(&mut self, x: usize) -> usize {
        let root = self.find(x);
        self.size[root]
    }
}

const MOD_P: usize = 1000000007;

#[allow(dead_code)]
// fact(n) = n! mod p
fn fact(n: usize) -> usize {
    let mut acc = 1;
    for i in 1..n + 1 {
        acc = acc * i % MOD_P;
    }
    acc
}

#[allow(dead_code)]
fn mod_pow(b: usize, mut e: usize) -> usize {
    let mut base = b;
    let mut acc = 1;

    while e > 1 {
        if e % 2 == 1 {
            acc = acc * base % MOD_P;
        }
        e /= 2;
        base = base * base % MOD_P;
    }

    if e == 1 {
        acc = acc * base % MOD_P;
    }

    acc
}

#[allow(dead_code)]
fn comb(n: usize, r: usize) -> usize {
    // nCr = n! / (r! (n-r)!) = n! (r!)^(p-2) ((n-r)!)^(p-2)
    let x = ((n - r + 1)..(n + 1)).fold(1, |p, x| p * x % MOD_P);
    let y = mod_pow(fact(r), MOD_P - 2);
    x * y % MOD_P
}

#[derive(Clone, Copy, Debug)]
struct GF(usize);

impl std::ops::Add for GF {
    type Output = GF;
    fn add(self, rhs: GF) -> Self::Output {
        let mut d = self.0 + rhs.0;
        if d >= MOD_P {
            d -= MOD_P;
        }
        GF(d)
    }
}

impl std::ops::AddAssign for GF {
    fn add_assign(&mut self, rhs: GF) {
        *self = *self + rhs;
    }
}

impl std::ops::Sub for GF {
    type Output = GF;
    fn sub(self, rhs: GF) -> Self::Output {
        let mut d = self.0 + MOD_P - rhs.0;
        if d >= MOD_P {
            d -= MOD_P;
        }
        GF(d)
    }
}

impl std::ops::SubAssign for GF {
    fn sub_assign(&mut self, rhs: GF) {
        *self = *self - rhs;
    }
}

impl std::ops::Mul for GF {
    type Output = GF;
    fn mul(self, rhs: GF) -> Self::Output {
        let mut d = self.0 * rhs.0;
        d %= MOD_P;
        GF(d)
    }
}

impl std::ops::MulAssign for GF {
    fn mul_assign(&mut self, rhs: GF) {
        *self = *self * rhs;
    }
}

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

#[allow(dead_code)]
impl GF {
    pub fn new(n: usize) -> GF {
        GF(n % MOD_P)
    }
    pub fn zero() -> GF {
        GF(0)
    }
    pub fn one() -> GF {
        GF(1)
    }
    pub fn pow(self, mut e: usize) -> GF {
        let mut acc = GF::one();
        let mut b = self;
        while e > 1 {
            if e % 2 == 1 {
                acc *= b;
            }
            b *= b;
            e /= 2;
        }
        if e == 1 {
            acc *= b;
        }
        acc
    }
    pub fn fact(self) -> GF {
        let mut acc = GF::one();
        for i in 1..=self.0 {
            acc *= GF::new(i);
        }
        acc
    }
    pub fn inv(self) -> GF {
        self.pow(MOD_P - 2)
    }
    pub fn comb(n: GF, r: GF) -> GF {
        // nCr = n! / (r! (n-r)!) = n! (r!)^(p-2) ((n-r)!)^(p-2)
        let x = ((n.0 - r.0 + 1)..=n.0).fold(GF::one(), |p, x| p * GF(x));
        let y = r.fact().inv();
        x * y
    }
}

#[allow(dead_code)]
#[derive(Debug)]
struct MemComb {
    inv: Vec<GF>,
    fact: Vec<GF>,
    factinv: Vec<GF>,
}

#[allow(dead_code)]
impl MemComb {
    pub fn new(n: usize) -> MemComb {
        let mut inv = vec![GF::one(); n + 1];
        let mut fact = vec![GF::one(); n + 1];
        let mut factinv = vec![GF::one(); n + 1];

        for i in 2..=n {
            fact[i] = fact[i - 1] * GF(i);
        }

        factinv[n] = fact[n].inv();
        for i in (1..n).rev() {
            factinv[i] = factinv[i + 1] * GF(i + 1); // 1/n! = 1/(n+1)! * (n+1)
            inv[i] = factinv[i] * fact[i - 1]; // 1/n = 1/n! * (n-1)!
        }
        inv[n] = factinv[n] * fact[n - 1];

        MemComb { inv, fact, factinv }
    }
    pub fn comb(&self, n: usize, r: usize) -> GF {
        if n >= r {
            self.fact[n] * self.factinv[r] * self.factinv[n - r]
        } else {
            GF::zero()
        }
    }
}

#[allow(dead_code)]
fn gcd(a: usize, b: usize) -> usize {
    if b > a {
        gcd(b, a)
    } else if a % b == 0 {
        b
    } else {
        gcd(b, a % b)
    }
}

#[allow(dead_code)]
fn getline() -> String {
    let mut __ret = String::new();
    std::io::stdin().read_line(&mut __ret).ok();
    return __ret;
}

#[allow(unused_imports)]
use std::cmp::{max, min};

fn main() {
    input! {
        n: usize,
        k: usize,
        a: [usize; n],
    }

    let mut v = vec![0; n];
    v[k - 1] = 1;
    for i in 0..k {
        v[k - 1] *= a[i];
    }
    for i in k..n {
        v[i] = v[i - 1] * a[i] / a[i - k];

        if v[i] > v[i - 1] {
            println!("Yes");
        } else {
            println!("No");
        }
    }
    // let ans = 0;
    // println!("{}", ans);
}

Submission Info

Submission Time
Task C - Marks
User sly
Language Rust (1.42.0)
Score 0
Code Size 7703 Byte
Status WA
Exec Time 351 ms
Memory 5048 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 300
Status
AC × 3
AC × 13
WA × 7
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
in01.txt AC 7 ms 1980 KB
in02.txt WA 196 ms 4376 KB
in03.txt WA 198 ms 4320 KB
in04.txt WA 197 ms 4272 KB
in05.txt WA 199 ms 4284 KB
in06.txt AC 351 ms 5048 KB
in07.txt WA 341 ms 4972 KB
in08.txt AC 55 ms 3620 KB
in09.txt AC 54 ms 3472 KB
in10.txt WA 196 ms 4380 KB
in11.txt AC 199 ms 4184 KB
in12.txt AC 217 ms 4348 KB
in13.txt AC 343 ms 5044 KB
in14.txt AC 51 ms 3588 KB
in15.txt WA 55 ms 3528 KB
in16.txt AC 5 ms 2116 KB
in17.txt AC 2 ms 2080 KB
sample_01.txt AC 3 ms 2056 KB
sample_02.txt AC 2 ms 2112 KB
sample_03.txt AC 2 ms 2056 KB