結果

問題 No.3371 Add Insert Operations
コンテスト
ユーザー rhoo
提出日時 2025-10-30 10:42:40
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 251 ms / 2,000 ms
コード長 2,011 bytes
コンパイル時間 12,689 ms
コンパイル使用メモリ 400,484 KB
実行使用メモリ 32,128 KB
最終ジャッジ日時 2025-11-17 20:41:23
合計ジャッジ時間 14,332 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(non_snake_case)]



fn main(){
    proconio::input!{
        n:usize,
        mut a:[usize;n],
    }

    use std::iter::*;
    let mut prev=once(!0).chain(0..n-1).collect::<Vec<_>>();
    let mut next=(1..n).chain(once(!0)).collect::<Vec<_>>();
    let mut que=(0..n).filter(|&i|a[i]==0).collect::<Vec<_>>();
    
    let mut perm=vec![!0;n];
    let mut it=0;
    
    while let Some(i)=que.pop(){
        perm[i]=it;
        it+=1;
        for ni in [prev[i],next[i]]{
            if ni==!0{
                continue;
            }
            if a[ni]==0{
                println!("0");
                return;
            }
            a[ni]-=1;
            if a[ni]==0{
                que.push(ni);
            }
        }

        if next[i]!=!0{
            prev[next[i]]=prev[i];
        }
        if prev[i]!=!0{
            next[prev[i]]=next[i];
        }
    }

    if it!=n{
        println!("0");
        return;
    }
    
    let mut pos=vec![!0;n];
    for i in 0..n{
        pos[perm[i]]=i;
    }

    const W:usize=512;
    let mut block=vec![!0;n/W];
    for i in 0..n/W{
        block[i]=*perm[i*W..(i+1)*W].iter().max().unwrap();
    }

    const MOD:u64=998244353;
    fn rec(perm:&[usize],block:&[usize],pos:&[usize],l:usize,r:usize)->u64{
        if l==r{
            return 1;
        }
        let mut max=0;
        let mut i=l;
        while i<r{
            if i%W==0 && i+W<r{
                max=max.max(block[i/W]);
                i+=W;
            } else{
                max=max.max(perm[i]);
                i+=1;
            }
        }
        let mi=pos[max];
        rec(perm,block,pos,l,mi)*rec(perm,block,pos,mi+1,r)%MOD*(r-l) as u64%MOD
    }

    let mut inv=1;
    let mut k=MOD-2;
    let mut pow2=rec(&perm,&block,&pos,0,n);
    while k>0{
        if k&1==1{
            inv=inv*pow2%MOD;
        }
        pow2=pow2*pow2%MOD;
        k>>=1;
    }

    let mut ans=inv;
    for i in 1..=n{
        ans=ans*i as u64%MOD;
    }

    println!("{ans}");
}
0