#1026707 (Rust) No.854 公平なりんご分配

提出ソース

結果

問題	No.854 公平なりんご分配
ユーザー	titia
提出日時	2024-11-15 08:50:47
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	444 ms / 3,153 ms
コード長	4,216 bytes
コンパイル時間	13,913 ms
コンパイル使用メモリ	390,628 KB
実行使用メモリ	108,304 KB
最終ジャッジ日時	2024-11-15 08:51:12
合計ジャッジ時間	24,470 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	1 ms 5,248 KB
testcase_03	AC	1 ms 5,248 KB
testcase_04	AC	1 ms 5,248 KB
testcase_05	AC	1 ms 5,248 KB
testcase_06	AC	1 ms 5,248 KB
testcase_07	AC	1 ms 5,248 KB
testcase_08	AC	1 ms 5,248 KB
testcase_09	AC	1 ms 5,248 KB
testcase_10	AC	1 ms 5,248 KB
testcase_11	AC	1 ms 5,248 KB
testcase_12	AC	1 ms 5,248 KB
testcase_13	AC	2 ms 5,248 KB
testcase_14	AC	1 ms 5,248 KB
testcase_15	AC	1 ms 5,248 KB
testcase_16	AC	1 ms 5,248 KB
testcase_17	AC	1 ms 5,248 KB
testcase_18	AC	1 ms 5,248 KB
testcase_19	AC	1 ms 5,248 KB
testcase_20	AC	1 ms 5,248 KB
testcase_21	AC	1 ms 5,248 KB
testcase_22	AC	3 ms 5,248 KB
testcase_23	AC	2 ms 5,248 KB
testcase_24	AC	4 ms 5,248 KB
testcase_25	AC	2 ms 5,248 KB
testcase_26	AC	5 ms 5,248 KB
testcase_27	AC	4 ms 5,248 KB
testcase_28	AC	3 ms 5,248 KB
testcase_29	AC	1 ms 5,248 KB
testcase_30	AC	2 ms 5,248 KB
testcase_31	AC	4 ms 5,248 KB
testcase_32	AC	36 ms 26,496 KB
testcase_33	AC	48 ms 15,488 KB
testcase_34	AC	80 ms 34,176 KB
testcase_35	AC	55 ms 28,160 KB
testcase_36	AC	48 ms 5,248 KB
testcase_37	AC	35 ms 25,216 KB
testcase_38	AC	26 ms 20,352 KB
testcase_39	AC	129 ms 36,096 KB
testcase_40	AC	58 ms 13,312 KB
testcase_41	AC	59 ms 23,680 KB
testcase_42	AC	67 ms 34,048 KB
testcase_43	AC	94 ms 24,448 KB
testcase_44	AC	93 ms 31,744 KB
testcase_45	AC	108 ms 7,936 KB
testcase_46	AC	126 ms 31,360 KB
testcase_47	AC	45 ms 18,688 KB
testcase_48	AC	61 ms 33,408 KB
testcase_49	AC	56 ms 34,048 KB
testcase_50	AC	30 ms 24,960 KB
testcase_51	AC	127 ms 32,768 KB
testcase_52	AC	88 ms 16,128 KB
testcase_53	AC	44 ms 15,872 KB
testcase_54	AC	85 ms 18,304 KB
testcase_55	AC	27 ms 16,000 KB
testcase_56	AC	23 ms 16,640 KB
testcase_57	AC	45 ms 13,696 KB
testcase_58	AC	98 ms 6,656 KB
testcase_59	AC	21 ms 12,288 KB
testcase_60	AC	59 ms 13,568 KB
testcase_61	AC	32 ms 5,248 KB
testcase_62	AC	72 ms 11,776 KB
testcase_63	AC	52 ms 12,672 KB
testcase_64	AC	20 ms 5,888 KB
testcase_65	AC	44 ms 30,336 KB
testcase_66	AC	43 ms 9,344 KB
testcase_67	AC	66 ms 20,224 KB
testcase_68	AC	73 ms 9,984 KB
testcase_69	AC	37 ms 36,224 KB
testcase_70	AC	24 ms 13,312 KB
testcase_71	AC	27 ms 14,336 KB
testcase_72	AC	65 ms 5,248 KB
testcase_73	AC	36 ms 25,472 KB
testcase_74	AC	80 ms 29,824 KB
testcase_75	AC	45 ms 14,336 KB
testcase_76	AC	62 ms 24,576 KB
testcase_77	AC	63 ms 33,280 KB
testcase_78	AC	94 ms 10,880 KB
testcase_79	AC	81 ms 20,736 KB
testcase_80	AC	75 ms 22,784 KB
testcase_81	AC	53 ms 23,680 KB
testcase_82	AC	250 ms 107,920 KB
testcase_83	AC	401 ms 107,920 KB
testcase_84	AC	392 ms 107,788 KB
testcase_85	AC	382 ms 44,432 KB
testcase_86	AC	149 ms 5,248 KB
testcase_87	AC	245 ms 107,792 KB
testcase_88	AC	248 ms 108,304 KB
testcase_89	AC	251 ms 107,932 KB
testcase_90	AC	250 ms 107,924 KB
testcase_91	AC	254 ms 108,048 KB
testcase_92	AC	444 ms 108,048 KB
testcase_93	AC	444 ms 107,916 KB

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

コンパイルメッセージ

warning: unused variable: `possible`
   --> src/main.rs:144:17
    |
144 |         let mut possible = true;
    |                 ^^^^^^^^ help: if this is intentional, prefix it with an underscore: `_possible`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: variable does not need to be mutable
   --> src/main.rs:144:13
    |
144 |         let mut possible = true;
    |             ----^^^^^^^^
    |             |
    |             help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: method `bisect_on_bit` is never used
  --> src/main.rs:38:8
   |
10 | impl BitIndexedTree {
   | ------------------- method in this implementation
...
38 |     fn bisect_on_bit(&self, mut x: i32) -> usize {
   |        ^^^^^^^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

ソースコード

raw source code

use std::io::{self, BufRead};
use std::collections::HashMap;

// Define a Binary Indexed Tree (Fenwick Tree) structure
struct BitIndexedTree {
    bit: Vec<i32>,
    len: usize,
}

impl BitIndexedTree {
    // Initialize the BIT with a given length
    fn new(len: usize) -> Self {
        BitIndexedTree {
            bit: vec![0; len + 1],
            len,
        }
    }

    // Update the BIT by adding `w` to index `v`
    fn update(&mut self, mut v: usize, w: i32) {
        while v <= self.len {
            self.bit[v] += w;
            v += v & (!v + 1);
        }
    }

    // Get the sum from index 1 to `v`
    fn get_value(&self, mut v: usize) -> i32 {
        let mut ans = 0;
        while v != 0 {
            ans += self.bit[v];
            v -= v & (!v + 1);
        }
        ans
    }

    // Find the first index where the sum is greater than or equal to `x`
    fn bisect_on_bit(&self, mut x: i32) -> usize {
        if x <= 0 {
            return 0;
        }

        let mut ans = 0;
        let mut h = 1 << (self.len.next_power_of_two().trailing_zeros());
        while h > 0 {
            if ans + h <= self.len && self.bit[ans + h] < x {
                x -= self.bit[ans + h];
                ans += h;
            }
            h /= 2;
        }
        ans + 1
    }
}

// Generate primes and sieve for factorization up to a given MAX
const MAX: usize = 2001;
fn generate_sieve() -> (Vec<usize>, Vec<i32>) {
    let mut sieve = vec![-1; MAX];
    let mut primes = Vec::new();

    for i in 2..MAX {
        if sieve[i] == -1 {
            primes.push(i);
            sieve[i] = i as i32;
        }
        for &p in &primes {
            if p * i >= MAX || p as i32 > sieve[i] {
                break;
            }
            sieve[p * i] = p as i32;
        }
    }
    (primes, sieve)
}

// Factorize a number using the generated sieve
fn factorize(mut x: usize, sieve: &[i32]) -> HashMap<usize, usize> {
    let mut factors = HashMap::new();
    while x != 1 {
        let k = sieve[x] as usize;
        *factors.entry(k).or_insert(0) += 1;
        x /= k;
    }
    factors
}

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();

    let n: usize = lines.next().unwrap().unwrap().trim().parse().unwrap();
    let a: Vec<usize> = lines
        .next()
        .unwrap()
        .unwrap()
        .split_whitespace()
        .map(|s| s.parse().unwrap())
        .collect();

    let (primes, sieve) = generate_sieve();
    let mut d = vec![-1; MAX];
    for (i, &prime) in primes.iter().enumerate() {
        d[prime] = i as i32;
    }

    let mut bit_list: Vec<BitIndexedTree> = (0..304).map(|_| BitIndexedTree::new(n + 3)).collect();

    for (i, &val) in a.iter().enumerate() {
        if val == 0 {
            bit_list[303].update(i + 2, 1);
            continue;
        }
        let factors = factorize(val, &sieve);
        for (factor, count) in factors {
            if d[factor] != -1 {
                bit_list[d[factor] as usize].update(i + 2, count as i32);
            }
        }
    }

    let q: usize = lines.next().unwrap().unwrap().trim().parse().unwrap();

    for _ in 0..q {
        let query: Vec<usize> = lines
            .next()
            .unwrap()
            .unwrap()
            .split_whitespace()
            .map(|s| s.parse().unwrap())
            .collect();
        let (mut p, l, r) = (query[0], query[1], query[2]);

        let zero_count = bit_list[303].get_value(r + 1) - bit_list[303].get_value(l);
        if zero_count > 0 {
            println!("Yes");
            continue;
        }
        if p == 1 {
            println!("Yes");
            continue;
        }

        let mut possible = true;
        for i in 0..303 {
            if p % primes[i] == 0 {
                let k = bit_list[i].get_value(r + 1) - bit_list[i].get_value(l);
                for _ in 0..k {
                    if p % primes[i] == 0 {
                        p /= primes[i];
                    } else {
                        break;
                    }
                }
            }
        }

        if p == 1 {
            println!("Yes");
        } else {
            println!("NO");
        }
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード