fork download
copy 
  1. #[allow(unused_imports)]
  2. use std::cmp::{max};
  3. use std::io::{BufWriter, stdin, stdout, Write};
  4.  
  5. #[derive(Default)]
  6. struct Scanner { buffer: Vec<String> }
  7. impl Scanner {
  8.     fn next<T: std::str::FromStr>(&mut self) -> T {
  9.         loop {
  10.             if let Some(tok) = self.buffer.pop() {
  11.                 return tok.parse().ok().expect("Failed parse");
  12.             }
  13.             let mut s = String::new();
  14.             stdin().read_line(&mut s).expect("Failed read");
  15.             self.buffer = s.split_whitespace().rev().map(String::from).collect();
  16.         }
  17.     }
  18. }
  19.  
  20. #[allow(unused_variables)]
  21. macro_rules! io_init {
  22.     ($scan:ident, $out:ident) => {
  23.         let mut $scan: Scanner = Scanner::default();
  24.         let $out = &mut BufWriter::new(stdout());
  25.     };
  26. }
  27.  
  28. macro_rules! read {
  29.     ($scan:ident, $($v:pat=>$t:ty),*) => { $(let $v=$scan.next::<$t>();)* };
  30. }
  31.  
  32. fn solve(scan: &mut Scanner, out: &mut BufWriter<std::io::Stdout>) {
  33.     let n = scan.next::<usize>();
  34.     let mut a = Vec::with_capacity(n);
  35.     for _ in 0..n {
  36.         a.push(scan.next::<i32>());
  37.     }
  38.     let mut l = 1usize;
  39.     let mut r = n + 1;
  40.     while l + 1 < r {
  41.         let mid = (l + r) >> 1;
  42.         let mut ok = 0i32;
  43.         let mut f = true;
  44.         let mut tag = vec![0i32; 2 * n];
  45.         for i in 0..n {
  46.             if !f { break; }
  47.             ok -= tag[i];
  48.             let tmp = if i + mid > n { (i + mid - n) } else { 0 };
  49.             if ok < tmp as i32 {
  50.                 f = false;
  51.                 break;
  52.             }
  53.             ok += 1;
  54.             let pos_i = i as i32 + a[i] + ok - tmp as i32;
  55.             let pos = pos_i as usize;
  56.             if pos < n {
  57.                 tag[pos] += 1;
  58.             }
  59.         }
  60.         if f {
  61.             l = mid;
  62.         } else {
  63.             r = mid;
  64.         }
  65.     }
  66.     writeln!(out, "{}", l).unwrap();
  67. }
  68.  
  69. fn main() {
  70.     io_init!(scan, out);
  71.     read!(scan, t=>i32);
  72.     for _ in 0..t {
  73.         solve(&mut scan, out);
  74.     }
  75. }
  76.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
8
2
1 2
4
2 1 0 0
10
5 9 3 7 1 5 1 5 4 3
10
1 1 1 1 1 1 1 1 1 1
10
3 2 1 0 3 2 1 0 3 2
5
5 2 0 5 5
1
1000000000
7
4 0 1 0 2 7 7
stdout
copy 
2
3
7
4
5
4
1
3
https://ideone.com/xFGOS3
language:
Rust (rust 1.56)
created:
16 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!