結果

問題 No.2182 KODOKU Stone
ユーザー akakimidoriakakimidori
提出日時 2023-04-13 04:10:44
言語 Rust
(1.77.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 1 ms
6,820 KB
testcase_03 AC 1 ms
6,816 KB
testcase_04 AC 1 ms
6,816 KB
testcase_05 AC 1 ms
6,816 KB
testcase_06 AC 1 ms
6,816 KB
testcase_07 AC 1 ms
6,820 KB
testcase_08 AC 1 ms
6,820 KB
testcase_09 AC 1 ms
6,816 KB
testcase_10 AC 1 ms
6,820 KB
testcase_11 AC 286 ms
15,152 KB
testcase_12 AC 82 ms
15,932 KB
testcase_13 AC 6 ms
6,820 KB
testcase_14 AC 10 ms
6,816 KB
testcase_15 AC 75 ms
16,104 KB
testcase_16 AC 74 ms
15,580 KB
testcase_17 AC 8 ms
6,820 KB
testcase_18 AC 94 ms
12,836 KB
testcase_19 AC 72 ms
7,512 KB
testcase_20 AC 95 ms
12,576 KB
testcase_21 AC 17 ms
6,820 KB
testcase_22 AC 7 ms
6,820 KB
testcase_23 AC 58 ms
6,816 KB
testcase_24 AC 31 ms
6,820 KB
testcase_25 AC 5 ms
6,816 KB
testcase_26 AC 5 ms
6,816 KB
testcase_27 AC 5 ms
6,816 KB
testcase_28 AC 76 ms
9,284 KB
testcase_29 AC 104 ms
13,256 KB
testcase_30 AC 118 ms
14,608 KB
testcase_31 AC 81 ms
9,584 KB
testcase_32 AC 90 ms
9,220 KB
testcase_33 AC 110 ms
13,100 KB
testcase_34 AC 28 ms
6,820 KB
testcase_35 AC 117 ms
13,056 KB
testcase_36 AC 22 ms
6,816 KB
testcase_37 AC 118 ms
14,624 KB
testcase_38 AC 1 ms
6,816 KB
testcase_39 AC 1 ms
6,816 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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);
}
0