結果

問題 No.5021 Addition Pyramid
ユーザー nephrologist
提出日時 2025-02-25 22:58:30
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1,902 ms / 2,000 ms
コード長 8,936 bytes
コンパイル時間 12,915 ms
コンパイル使用メモリ 401,636 KB
実行使用メモリ 6,820 KB
スコア 13,463,905
最終ジャッジ日時 2025-02-25 23:00:23
合計ジャッジ時間 112,224 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unexpected `cfg` condition value: `local`
   --> src/main.rs:196:15
    |
196 |         #[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:200:19
    |
200 |         #[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

warning: value assigned to `newidx` is never read
  --> src/main.rs:42:17
   |
42 |         let mut newidx = 0;
   |                 ^^^^^^
   |
   = help: maybe it is overwritten before being read?
   = note: `#[warn(unused_assignments)]` on by default

ソースコード

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;
const TIME_LIMIT: f64 = 1.9;
fn main() {
    let inp = get_input();
    let mut rnd = XorShift::new(20250225);
    let mut state = State::new(&inp);
    // state.change(&inp, inp.n - 3, 10);
    solve2(&mut state, &inp, &mut rnd);
    state.print(&inp);
    state.calc_score(&inp);
    // eprintln!("{:?}", state.now.data.clone());
}

fn solve(state: &mut State, inp: &Input, rnd: &mut XorShift) {
    for i in 0..inp.n {
        // let idx = to_index(inp.n - 1, i);
        state.change(inp, i, inp.AA[inp.n - 1][i])
    }
}

fn solve2(state: &mut State, inp: &Input, rnd: &mut XorShift) {
    let mut best = state.clone();
    while TIME_LIMIT > get_time() {
        let newval = rnd.gen_range(0, 100000000);
        let mut newidx = 0;
        if rnd.next() % 2 == 0 {
            newidx = rnd.gen_range(0, inp.n);
        } else {
            let hoge = state.now.query(0, NUM).0;
            let left = to_ij(hoge).0;
            let right = (left + rnd.gen_range(1, 5)).min(inp.n);
            // eprintln!("left right {} {}", left, right);
            newidx = rnd.gen_range(left, right);
        }

        // eprintln!("newval {} newidx {}", newval, newidx);
        let idx = to_index(inp.n - 1, newidx);
        // eprintln!("idx {}", idx);
        let preval = state.now.get(idx).1;
        let prescore = state.score;
        state.change(inp, newidx, newval);
        let nexscore = state.score;
        if prescore > nexscore {
            state.change(inp, newidx, preval);
        }
    }
}
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>>,
}
#[derive(Clone)]
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 mut values = vec![];
        for idx in 0..NUM {
            let (i, j) = to_ij(idx);
            // eprintln!("ij {} {}", i, j);
            values.push((idx, 0, inp.AA[i][j]));
        }

        let mut now = SegmentTree::build(values);

        let mut score = 0;
        score += calc_edge(now.query(0, NUM));
        eprintln!("initial {}", 50000000 - score);
        Self { bottom, now, score }
    }
    fn calc_score(&self, inp: &Input) {
        let mx = calc_edge(self.now.query(0, NUM));

        eprintln!("Score {}", 50000000 - mx);
        // assert_eq!(mx, self.score);
    }
    fn recalc_score(&mut self, inp: &Input) {
        let mx = calc_edge(self.now.query(0, NUM));
        self.score = 50000000 - mx;
        // eprintln!("Score {}", mx);
        // assert_eq!(mx, self.score);
    }
    fn change(&mut self, inp: &Input, idx: usize, delta: usize) {
        let mut haba = 1;
        let index = to_index(inp.n - 1, idx);
        // let mut newval = self.now.get(index).1;
        // newval += delta;
        let newval = delta;
        self.now.data[self.now.size + index] =
            (self.now.get(index).0, newval, self.now.get(index).2);
        for i in (0..inp.n - 1).rev() {
            for j in idx - haba..=idx.min(i) {
                let idx = to_index(i, j);
                let idx1 = to_index(i + 1, j);
                let idx2 = to_index(i + 1, j + 1);
                let mut newval = self.now.get(idx1).1 + self.now.get(idx2).1;

                if newval >= MOD {
                    newval -= MOD;
                }
                self.now.update(idx, newval);
                // eprintln!("i j {} {}", i, j);
            }
            if idx - haba > 0 {
                haba += 1;
            }
        }
        self.recalc_score(inp);
    }
    fn print(&self, inp: &Input) {
        for i in 0..inp.n {
            let idx = to_index(inp.n - 1, 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
        }
    }
}
#[derive(Clone)]
struct SegmentTree {
    size: usize,
    data: Vec<(usize, usize, usize)>, // (index, value,AA)
}

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

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

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

        // 下から上へマージして構築
        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;
        let pre = self.data[pos].2;
        self.data[pos] = (pos - self.size, value, pre);
        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, usize) {
        self.data[idx + self.size]
    }
    /// 区間 [l, r) の最大値 (index, value) を取得
    fn query(&self, mut l: usize, mut r: usize) -> (usize, usize, usize) {
        l += self.size;
        r += self.size;
        let mut res_left = (0, 0, 0);
        let mut res_right = (0, 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, usize), b: (usize, usize, usize)) -> (usize, usize, usize) {
        let v1 = calc_edge(a);
        let v2 = calc_edge(b);
        if v1 >= v2 {
            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)
}

fn calc_edge(hoge: (usize, usize, usize)) -> usize {
    let v1 = hoge.1.abs_diff(hoge.2);
    let v2 = MOD.abs_diff(v1);
    v1.min(v2)
}
0