結果

問題 No.5021 Addition Pyramid
ユーザー nephrologist
提出日時 2025-02-25 21:36:13
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 6,636 bytes
コンパイル時間 27,702 ms
コンパイル使用メモリ 406,080 KB
実行使用メモリ 6,820 KB
スコア 2,074,947
最終ジャッジ日時 2025-02-25 21:36:51
合計ジャッジ時間 15,210 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unexpected `cfg` condition value: `local`
   --> src/main.rs:141:15
    |
141 |         #[cfg(feature = "local")]
    |               ^^^^^^^^^^^^^^^^^ help: remove the condition
    |
    = note: no expected values for `feature`
    = help: consider adding `local` as a feature in `Cargo.toml`
    = note: see <https://doc.rust-lang.org/nightly/rustc/check-cfg/cargo-specifics.html> for more information about checking conditional configuration
    = note: `#[warn(unexpected_cfgs)]` on by default

warning: unexpected `cfg` condition value: `local`
   --> src/main.rs:145:19
    |
145 |         #[cfg(not(feature = "local"))]
    |                   ^^^^^^^^^^^^^^^^^ help: remove the condition
    |
    = note: no expected values for `feature`
    = help: consider adding `local` as a feature in `Cargo.toml`
    = note: see <https://doc.rust-lang.org/nightly/rustc/check-cfg/cargo-specifics.html> for more information about checking conditional configuration

ソースコード

diff # 

#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_variables)]
#![allow(unused_mut)]
#![allow(non_upper_case_globals)]
// use itertools::*;
use proconio::input;
use proconio::marker::*;
use proconio::*;
// use rand::prelude::*;
// use rand_pcg::*;
use std::collections::*;
use std::collections::{HashSet, VecDeque};
use std::ops::*;

const MOD: usize = 100000000;
const NUM: usize = 25 * 51;
fn main() {
    let inp = get_input();
    let mut rnd = XorShift::new(20250225);
    let mut state = State::new(&inp);
    // solve(&mut state, &inp, &mut rnd);
    state.print(&inp);
}

struct XorShift {
    state: usize,
}

impl XorShift {
    fn new(seed: usize) -> Self {
        let state = if seed != 0 { seed } else { 2463534242 }; // 0回避
        Self { state }
    }

    fn next(&mut self) -> usize {
        let mut x = self.state;
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
        self.state = x;
        x
    }
    fn gen_range(&mut self, left: usize, right: usize) -> usize {
        self.next() % (right - left) + left
    }
}

pub struct Input {
    n: usize,
    AA: Vec<Vec<usize>>,
}
pub struct State {
    bottom: Vec<usize>,
    now: SegmentTree,
    score: usize,
}
impl State {
    fn new(inp: &Input) -> Self {
        let mut bottom = vec![0; inp.n];
        let num = inp.n * inp.n / 2 + 50;

        let values: Vec<(usize, usize)> = (0..num).map(|i| (i, 0)).collect();

        let mut now = SegmentTree::build(values);
        let mut score = 0;
        Self { bottom, now, score }
    }
    fn calc_score(&self, inp: &Input) {
        let mut mx = 0;
        for i in 0..inp.n {
            for j in 0..=i {
                let val1 = inp.AA[i][j].abs_diff(self.now.get(to_index(i, j)).1);
                let val2 = val1.abs_diff(MOD);
                mx = mx.max(val1.min(val2));
            }
        }
        eprintln!("Score {}", mx);
        assert_eq!(mx, self.score);
    }
    fn change(&mut self, inp: &Input, idx: usize, delta: usize) {
        let mut haba = 0;
        for i in (0..inp.n).rev() {
            for j in idx - haba..=idx.min(i) {
                let idx = to_index(i, j);
                let mut newval = self.now.get(idx).1;
                newval += delta;
                if newval > MOD {
                    newval -= MOD;
                }
                self.now.update(idx, newval);
                // eprintln!("i j {} {}", i, j);
            }
            if idx - haba > 0 {
                haba += 1;
            }
        }
    }
    fn print(&self, inp: &Input) {
        for i in 0..inp.n {
            let idx = to_index(inp.n, i);
            if i == inp.n - 1 {
                println!("{}", self.now.get(idx).1)
            } else {
                print!("{} ", self.now.get(idx).1);
            }
        }
    }
    fn get_worst_idx(&self) -> (usize, usize) {
        self.now.query(0, NUM)
    }
    // fn get_candidate_idx(&self) -> usize {}
    // fn gather_vals(&self, idx:usize){
    //     for i in
    // }
}
fn get_input() -> Input {
    input! {n:usize};
    let mut AA = vec![];
    for i in 0..n {
        input! {temp:[usize;i+1]};
        AA.push(temp);
    }
    Input { n, AA }
}

pub fn get_time() -> f64 {
    static mut STIME: f64 = -1.0; // 初期値
    let t = std::time::SystemTime::now() // nowを取得
        .duration_since(std::time::UNIX_EPOCH)
        .unwrap();
    // a.duration_since(b)だとa>bが前提
    let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
    // as_secsが秒, .subsec_nanos()が小数点以下の秒
    unsafe {
        if STIME < 0.0 {
            STIME = ms; // 経過時間の初期化
        }
        // ローカル環境とジャッジ環境の実行速度差はget_timeで吸収しておくと便利
        #[cfg(feature = "local")]
        {
            (ms - STIME) * 1.3
        }
        #[cfg(not(feature = "local"))]
        {
            ms - STIME
        }
    }
}
struct SegmentTree {
    size: usize,
    data: Vec<(usize, usize)>, // (index, value)
}

impl SegmentTree {
    /// 新規作成 (空のセグメントツリー)
    fn new(n: usize) -> Self {
        let size = n.next_power_of_two();
        Self {
            size,
            data: vec![(0, 0); 2 * size],
        }
    }

    /// (index, value) の Vec から SegmentTree を構築
    fn build(values: Vec<(usize, usize)>) -> Self {
        let n = values.len();
        let size = n.next_power_of_two();
        let mut seg_tree = Self {
            size,
            data: vec![(0, 0); 2 * size],
        };

        // リーフノードにデータをセット
        for (i, &(index, value)) in values.iter().enumerate() {
            seg_tree.data[i + size] = (index, value);
        }

        // 下から上へマージして構築
        for i in (1..size).rev() {
            seg_tree.data[i] = seg_tree.merge(seg_tree.data[2 * i], seg_tree.data[2 * i + 1]);
        }

        seg_tree
    }

    /// 値を更新 (pos 番目の要素を value にする)
    fn update(&mut self, mut pos: usize, value: usize) {
        pos += self.size;
        self.data[pos] = (pos - self.size, value);
        while pos > 1 {
            pos /= 2;
            self.data[pos] = self.merge(self.data[2 * pos], self.data[2 * pos + 1]);
        }
    }
    fn get(&self, idx: usize) -> (usize, usize) {
        self.data[idx + self.size]
    }
    /// 区間 [l, r) の最大値 (index, value) を取得
    fn query(&self, mut l: usize, mut r: usize) -> (usize, usize) {
        l += self.size;
        r += self.size;
        let mut res_left = (0, 0);
        let mut res_right = (0, 0);

        while l < r {
            if l % 2 == 1 {
                res_left = self.merge(res_left, self.data[l]);
                l += 1;
            }
            if r % 2 == 1 {
                r -= 1;
                res_right = self.merge(self.data[r], res_right);
            }
            l /= 2;
            r /= 2;
        }
        self.merge(res_left, res_right)
    }

    /// 2 つのノードをマージする (valueが大きい方を選択)
    fn merge(&self, a: (usize, usize), b: (usize, usize)) -> (usize, usize) {
        if a.1 >= b.1 {
            a
        } else {
            b
        }
    }
}

/// (i, j) -> idx 変換 (O(1))
fn to_index(i: usize, j: usize) -> usize {
    (i * (i + 1)) / 2 + j
}

/// idx -> (i, j) 変換 (O(1))
fn to_ij(idx: usize) -> (usize, usize) {
    // i を求める
    let i = ((-1.0 + (1.0 + 8.0 * idx as f64).sqrt()) / 2.0).floor() as usize;
    let j = idx - (i * (i + 1)) / 2;
    (i, j)
}
0