Submission #49298848

---

Source Code Expand

// -*- coding:utf-8-unix -*-
/*
このコード、と～おれ!
  ∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂    ノ       ・゜+.
 しーＪ       °。+ *´¨)
                  .· ´¸.·*´¨) ¸.·*¨)
                                      (¸.·´ (¸.·'* ☆
*/

use ac_library::*;
use itertools::Itertools;
use num_traits::Num;
use proconio::input;
use proconio::marker::Chars;
use std::cmp::Reverse;
use std::collections::BinaryHeap;

static INF: usize = 1e18 as usize;

trait Vector<T> {
    fn insertion_sort(&mut self, elem: T);
    fn print_continuous(&self);
    fn print_space_separate(&self);
    fn print_linebreak(&self);
}

impl<T: std::cmp::Ord  + std::fmt::Display> Vector<T> for Vec<T> {
    /* 挿入ソート
    小数型(より正確にはNaNを持つ型？)に対しては適用できない。
    */
    fn insertion_sort(&mut self, elem: T) {
        let idx = self.binary_search(&elem).unwrap_or_else(|x| x);
        self.insert(idx, elem);
    }

    // 空白無しで全要素を一行出力
    fn print_continuous(&self) {
        for i in 0..self.len() {
            print!("{}", self[i]);
        }
        println!()
    }

    // 空白区切りで一行出力
    fn print_space_separate(&self) {
        for i in 0..self.len() {
            print!("{}", self[i]);
            if i != self.len()-1 { print!(" ") }
        }
        println!()
    }

    // 改行して出力
    fn print_linebreak(&self) {
        for i in 0..self.len() {
            println!("{}", self[i]);
        }
    }
}

#[derive(Clone)]
struct Edge<T> where T: Num {
    to: usize,
    cost: T
}

struct Graph<T> where T: From<usize> + Num{
    graph: Vec<Vec<Edge<T>>>,
}

impl<T> Graph<T> where T: From<usize> + Num + Clone + Ord {
    fn new(size: usize) -> Graph<T> {
        let graph :Vec<Vec<Edge<T>>> = vec![vec![]; size];
        Graph{ graph }
    }

    // 1-index で与えられることを想定
    fn add(&mut self, from: usize, to: usize, cost: T) {
        self.graph[from - 1].push(Edge{to: to - 1, cost});
    }

    fn dijkstra(&mut self, start: usize) -> Vec<T> {
        let mut distance = vec![INF.into(); self.graph.len()];
        let mut heap:BinaryHeap<Reverse<(T, usize)>> = BinaryHeap::new();
        heap.push(Reverse((0.into(), start)));

        while let Some(Reverse((cost, pos))) = heap.pop() {
            if distance[pos] != INF.into() { continue; }
            distance[pos] = cost.clone();
            
            for edge in &self.graph[pos] {
                if distance[edge.to] != INF.into() { continue; }
                heap.push(Reverse((cost.clone() + edge.cost.clone().into() , edge.to)));
            }
        }
        distance
    }
}

struct SegmentTree<T> where T: From<usize> + Num + Copy + Ord, {
    n: usize,   // 要素数
    dat: Vec<T> // 実際のデータ
}

/* RangeMinQuery。isize or usizeでなければオーバーフローするので注意*/
#[allow(dead_code)]
impl<T> SegmentTree<T> where T:From<usize> + Num + Copy + Ord, {
    pub fn new(n: usize, data: &Vec<T>) -> SegmentTree<T> {
        let mut x = 1;
        while n > x {
            x *= 2;
        }

        let size = 2 * x - 1;
        let mut dat :Vec<T> = vec![T::from(INF); size];
        for i in 0..n {
            dat[size - n + i] = data[i];
        }

        SegmentTree { n: x, dat }
    }

    /* 配列のidx番目の値を更新する */
    pub fn update(&mut self, mut idx: usize, x: T) {
        idx += self.n - 1; // セグ木上でのインデックスに変換
        self.dat[idx] = x;

        while idx > 0 {   // 親ノードの更新
            idx = (idx - 1) / 2;
            self.dat[idx] = self.evaluate(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2]);
        }
    }

    /* 半開区間[a, b)で値を取得する */
    pub fn query(&self, a: usize, b: usize) -> T {
        self.sub_query(a, b, 0, 0, self.n)
    }

    fn sub_query(&self, a: usize, b: usize, node: usize, l: usize, r: usize) -> T {
        return if r <= a || b <= l {
            // 範囲外の処理
            T::from(INF)
        } else if a <= l && r <= b {
            // 範囲内ならば今のノードを返す
            self.dat[node]
        } else {
            // 一部区間がかぶるなら半分に分割してそれぞれの最小値を得る
            let mid = (l + r) / 2;
            let vl = self.sub_query(a, b, node * 2 + 1, l, mid);
            let vr = self.sub_query(a, b, node * 2 + 2, mid, r);

            self.evaluate(vl, vr)
        }
    }

    fn evaluate(&self, a: T, b: T) -> T {
        a.min(b)
    }
}


fn solve(){
    input! {
        n: usize,
        a: [usize; n]
    }

    let mut dp = vec![INF; n];
    for i in 0..n {
        dp[i] = (i+1).min(a[i]);
        if i != 0 {
            dp[i] = dp[i].min(dp[i-1] + 1);
        }
    }

    for i in (0..n).rev() {
        dp[i] = dp[i].min(n - i).min(a[i]);
        if i != n-1 {
            dp[i] = dp[i].min(dp[i+1] + 1);
        }
    }
    let &x = dp.iter().max().unwrap();
    println!("{}", x);

}

fn main() {
    let mut i: usize = 1;

/*    /* 複数テストケースならコメントアウトを外す */
    let mut input = String::new();
    io::stdout().flush().unwrap();
    io::stdin().read_line(&mut input).unwrap();
    i = input.trim().parse().unwrap();*/

    while i != 0 {
        solve();
        i -= 1;
    }
}

Submission Info

Compile Error

warning: unused import: `ac_library::*`
  --> src/main.rs:12:5
   |
12 | use ac_library::*;
   |     ^^^^^^^^^^^^^
   |
   = note: `#[warn(unused_imports)]` on by default

warning: unused import: `itertools::Itertools`
  --> src/main.rs:13:5
   |
13 | use itertools::Itertools;
   |     ^^^^^^^^^^^^^^^^^^^^

warning: unused import: `proconio::marker::Chars`
  --> src/main.rs:16:5
   |
16 | use proconio::marker::Chars;
   |     ^^^^^^^^^^^^^^^^^^^^^^^

warning: fields `to` and `cost` are never read
  --> src/main.rs:65:5
   |
64 | struct Edge<T> where T: Num {
   |        ---- fields in this struct
65 |     to: usize,
   |     ^^
66 |     cost: T
   |     ^^^^
   |
   = note: `Edge` has a derived impl for the trait `Clone`, but this is intentionally ignored during dead code analysis
   = note: `#[warn(dead_code)]` on by default

warning: struct `Graph` is never constructed
  --> src/main.rs:69:8
   |
69 | struct Graph<T> where T: From<usize> + Num{
   |        ^^^^^

warning: associated items `new`, `add`, and `dijkstra` are never used
  --> src/main.rs:74:8
   |
73 | impl<T> Graph<T> where T: From<usize> + Num + Clone + Ord {
   | ---------------- associated items in this implementation
74 |     fn new(size: usize) -> Graph<T> {
   |        ^^^
...
80 |     fn add(&mut self, from: usize, to: usize, cost: T) {
   |        ^^^
...
84 |     fn dijkstra(&mut self, start: usize) -> Vec<T> {
   |        ^^^^^^^^

Judge Result