結果

問題 No.1170 Never Want to Walk
コンテスト
ユーザー srtry
提出日時 2026-01-11 17:05:28
言語 Rust
(1.92.0 + proconio + num)
結果
AC  
実行時間 93 ms / 2,000 ms
コード長 2,467 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 27,265 ms
コンパイル使用メモリ 412,232 KB
実行使用メモリ 19,756 KB
最終ジャッジ日時 2026-01-11 17:06:37
合計ジャッジ時間 30,730 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/* 
 *     Author:  srtry
 *     Created: 2026-01-10T16:34:04+09:00
 *     Coding:  utf-8-unix
 */

use proconio::input;
use std::io::{stdout,Write,BufWriter};
use std::collections::{VecDeque,BTreeSet,BTreeMap};

const BUFFSIZE:usize = 10000;
fn main() {
    input!{
        n:usize, a:usize, b:usize,
        x:[usize;n]
    }

    let out = stdout();
    let mut out = BufWriter::new(out.lock());
    
    let mut queue:BTreeMap<usize,usize> = x.iter().enumerate().map(|(i,&v)| (v,i)).collect();
    let mut group:BTreeSet<usize> = BTreeSet::new();  // indices
    let mut ans_vec:Vec<usize> = vec![0;n];
    let mut cnt = 0;

    loop {
        let mut subqueue:VecDeque<(usize,usize)> = VecDeque::new();   //index
        group.clear();
        if cnt == n {
            break;
        }    
        
        let (v,i) = queue.pop_first().unwrap();
        subqueue.push_back((v,i));
        
        loop {
            let from:(usize,usize);
            if let Some(y) = subqueue.pop_front() {
                from = y.clone();
            } else {
                let size = group.len();
                group.iter().for_each(|&i| ans_vec[i]=size);
                cnt += size;
                break;
            }

            // 後ろに探索
            let mut will_remove:BTreeSet<usize> = BTreeSet::new();
            for (&v,&i) in queue.range(from.0..) {
                let dist = v - from.0;
                if dist > b {
                    break;
                }
                if dist >= a {
                    subqueue.push_back((v,i));
                    will_remove.insert(v);
                }
            }

            // 前に探索
            for (&v,&i) in queue.range(0..from.0).rev() {
                let dist = from.0 - v;
                if dist > b {
                    break;
                }
                if dist >= a {
                    subqueue.push_back((v,i));
                    will_remove.insert(v);
                }
            }

            will_remove.iter().for_each(|&v| {queue.remove(&v);});
            will_remove.clear();
            group.insert(from.1);
        }
    }

    let ans_str_vec = {
        let mut vec:Vec<String> = vec![String::from("");n/BUFFSIZE + 1];
        for (i,&v) in ans_vec.iter().enumerate() {
            vec[i/BUFFSIZE] += &(v.to_string() + "\n");
        }
        vec
    };
    for e in ans_str_vec.iter() {
        out.write_all(e.as_bytes()).unwrap();
    };
}
0