#858743 (Rust) No.2182 KODOKU Stone

• 問題: No.2182 KODOKU Stone
• ユーザー: akakimidori
• 提出日時: 2023-04-13 04:10:44
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 283 ms / 2,000 ms
• コード長: 7,373 bytes
• コンパイル時間: 1,196 ms
• コンパイル使用メモリ: 169,448 KB
• 実行使用メモリ: 16,048 KB
• 最終ジャッジ日時: 2024-04-17 11:11:37
• 合計ジャッジ時間: 4,412 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	1 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	283 ms; 15,272 KB
testcase_12	AC	83 ms; 15,824 KB
testcase_13	AC	6 ms; 5,376 KB
testcase_14	AC	9 ms; 5,376 KB
testcase_15	AC	72 ms; 16,048 KB
testcase_16	AC	73 ms; 15,780 KB
testcase_17	AC	8 ms; 5,376 KB
testcase_18	AC	97 ms; 12,828 KB
testcase_19	AC	71 ms; 7,504 KB
testcase_20	AC	92 ms; 12,444 KB
testcase_21	AC	16 ms; 5,376 KB
testcase_22	AC	7 ms; 5,376 KB
testcase_23	AC	59 ms; 5,756 KB
testcase_24	AC	31 ms; 5,376 KB
testcase_25	AC	5 ms; 5,376 KB
testcase_26	AC	5 ms; 5,376 KB
testcase_27	AC	5 ms; 5,376 KB
testcase_28	AC	73 ms; 9,284 KB
testcase_29	AC	104 ms; 13,396 KB
testcase_30	AC	115 ms; 14,656 KB
testcase_31	AC	80 ms; 9,584 KB
testcase_32	AC	88 ms; 9,348 KB
testcase_33	AC	109 ms; 13,060 KB
testcase_34	AC	25 ms; 5,376 KB
testcase_35	AC	113 ms; 12,912 KB
testcase_36	AC	20 ms; 5,376 KB
testcase_37	AC	117 ms; 14,620 KB
testcase_38	AC	1 ms; 5,376 KB
testcase_39	AC	1 ms; 5,376 KB

コンパイルメッセージ

warning: unused variable: `out`
   --> main.rs:200:45
    |
200 | fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {
    |                                             ^^^ help: if this is intentional, prefix it with an underscore: `_out`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: 1 warning emitted

ソースコード

// k[n - 1] 以上があるなら終わり
// ない時
// 1を持ち越さないとダメ
// 全部1 or 1をk[n - 1] - 1 個もつようなやつを最後にもって来たい
// どっちがいいのか？
// どっちもありそう
// inf 2 inf
// 0 1 110
// とかは 0 110 1 と置くしかない
// 
// どっかで1を生成して、それを運ぶイメージ
// 1のみを使用する場合はサイズが最も小さいやつを使うのが良さげ
// k_{n-1}-1個のやつはなんでもいい感
// 全部1のみの個数をcとして
// 末尾c+1項のk_i の最小値が0を含む最大値以下なら可能
// そこに最大値置いて、以降1のみを埋めればいい
// ない時
// 最大値が持ち越せるようなところにそれを置く
// ...
// なんとかなりそう?
// WA
// 先頭に置く場合がなんか壊れてそう
// 

// ---------- begin segment tree Point Update Range Query ----------
pub struct SegmentTreePURQ<T, F> {
    n: usize,
    size: usize,
    data: Vec<T>,
    e: T,
    op: F,
}

impl<T, F> SegmentTreePURQ<T, F>
where
    T: Clone,
    F: Fn(&T, &T) -> T,
{
    pub fn new(n: usize, e: T, op: F) -> Self {
        assert!(n > 0);
        let size = n.next_power_of_two();
        let data = vec![e.clone(); 2 * size];
        SegmentTreePURQ {
            n,
            size,
            data,
            e,
            op,
        }
    }
    pub fn update_tmp(&mut self, x: usize, v: T) {
        assert!(x < self.n);
        self.data[x + self.size] = v;
    }
    pub fn update_all(&mut self) {
        for i in (1..self.size).rev() {
            self.data[i] = (self.op)(&self.data[2 * i], &self.data[2 * i + 1]);
        }
    }
    pub fn update(&mut self, x: usize, v: T) {
        assert!(x < self.n);
        let mut x = x + self.size;
        self.data[x] = v;
        x >>= 1;
        while x > 0 {
            self.data[x] = (self.op)(&self.data[2 * x], &self.data[2 * x + 1]);
            x >>= 1;
        }
    }
    pub fn find(&self, l: usize, r: usize) -> T {
        assert!(l <= r && r <= self.n);
        if l == r {
            return self.e.clone();
        }
        let mut l = self.size + l;
        let mut r = self.size + r;
        let mut x = self.e.clone();
        let mut y = self.e.clone();
        while l < r {
            if l & 1 == 1 {
                x = (self.op)(&x, &self.data[l]);
                l += 1;
            }
            if r & 1 == 1 {
                r -= 1;
                y = (self.op)(&self.data[r], &y);
            }
            l >>= 1;
            r >>= 1;
        }
        (self.op)(&x, &y)
    }
    pub fn max_right<P>(&self, l: usize, f: P) -> usize
    where
        P: Fn(&T) -> bool,
    {
        assert!(l <= self.n);
        assert!(f(&self.e));
        if l == self.n {
            return self.n;
        }
        let mut l = l + self.size;
        let mut sum = self.e.clone();
        while {
            l >>= l.trailing_zeros();
            let v = (self.op)(&sum, &self.data[l]);
            if !f(&v) {
                while l < self.size {
                    l <<= 1;
                    let v = (self.op)(&sum, &self.data[l]);
                    if f(&v) {
                        sum = v;
                        l += 1;
                    }
                }
                return l - self.size;
            }
            sum = v;
            l += 1;
            l.count_ones() > 1
        } {}
        self.n
    }
    pub fn min_left<P>(&self, r: usize, f: P) -> usize
    where
        P: Fn(&T) -> bool,
    {
        assert!(r <= self.n);
        assert!(f(&self.e));
        if r == 0 {
            return 0;
        }
        let mut r = r + self.size;
        let mut sum = self.e.clone();
        while {
            r -= 1;
            while r > 1 && r & 1 == 1 {
                r >>= 1;
            }
            let v = (self.op)(&self.data[r], &sum);
            if !f(&v) {
                while r < self.size {
                    r = 2 * r + 1;
                    let v = (self.op)(&self.data[r], &sum);
                    if f(&v) {
                        sum = v;
                        r -= 1;
                    }
                }
                return r + 1 - self.size;
            }
            sum = v;
            (r & (!r + 1)) != r
        } {}
        0
    }
}
// ---------- end segment tree Point Update Range Query ----------
// ---------- begin scannner ----------
#[allow(dead_code)]
mod scanner {
    use std::str::FromStr;
    pub struct Scanner<'a> {
        it: std::str::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 {
            self.it.next().unwrap().parse::<T>().ok().unwrap()
        }
        pub fn next_bytes(&mut self) -> Vec<u8> {
            self.it.next().unwrap().bytes().collect()
        }
        pub fn next_chars(&mut self) -> Vec<char> {
            self.it.next().unwrap().chars().collect()
        }
        pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
            (0..len).map(|_| self.next()).collect()
        }
    }
}
// ---------- end scannner ----------

use std::io::Write;

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut sc = scanner::Scanner::new(&s);
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    run(&mut sc, &mut out);
}

fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {
    let n: usize = sc.next();
    let k: Vec<usize> = sc.next_vec(n);
    let mut a = vec![];
    for _ in 0..n {
        let t: usize = sc.next();
        let v: Vec<u32> = sc.next_vec(t);
        a.push(v);
    }
    let can = |m: u32| -> bool {
        let mut x = vec![];
        let mut y = vec![];
        for a in a.iter() {
            let cnt = a.iter().filter(|a| **a >= m).count();
            if cnt == a.len() {
                y.push(cnt);
            } else {
                x.push(cnt);
            }
        }
        x.sort();
        y.sort();
        let mut rmq = SegmentTreePURQ::new(n, (std::usize::MAX / 2, 0), |a, b| std::cmp::min(*a, *b));
        for (i, k) in k.iter().enumerate() {
            rmq.update_tmp(i, (*k, !i));
        }
        rmq.update_all();
        while !x.is_empty() {
            if y.len() > 0 {
                let len = y.len();
                let v = rmq.find(x.len(), n);
                if v.0 <= y[len - 1] {
                    return true;
                }
            }
            let len = x.len();
            let v = rmq.find(x.len() - 1, n);
            if v.0 <= x[len - 1] {
                return true;
            }
            if v.0 > x[len - 1] + 1 {
                return false;
            }
            if !v.1 == 0 {
                return false;
            }
            x.pop();
            rmq.update(!v.1, (std::usize::MAX / 2, 0));
        }
        true
    };
    let mut ok = 1;
    let mut ng = 10u32.pow(9) + 1;
    while ng - ok > 1 {
        let mid = (ok + ng) / 2;
        if can(mid) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    println!("{}", ok);
}