結果

問題 No.2182 KODOKU Stone
ユーザー akakimidori
提出日時 2023-04-13 04:10:44
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 286 ms / 2,000 ms
コード長 7,373 bytes
コンパイル時間 13,082 ms
コンパイル使用メモリ 398,980 KB
実行使用メモリ 16,104 KB
最終ジャッジ日時 2024-10-09 05:16:14
合計ジャッジ時間 15,534 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `out`
   --> src/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

ソースコード

diff #
プレゼンテーションモードにする

// 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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0