#1019431 (Rust) No.919 You Are A Project Manager

提出ソース

結果

問題	No.919 You Are A Project Manager
ユーザー	CoCo_Japan_pan
提出日時	2024-10-14 13:05:35
言語	Rust (1.77.0 + proconio)
結果	WA
実行時間	-
コード長	12,186 bytes
コンパイル時間	17,737 ms
コンパイル使用メモリ	387,908 KB
実行使用メモリ	6,824 KB
最終ジャッジ日時	2024-10-14 13:05:56
合計ジャッジ時間	18,497 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	8 ms 5,248 KB
testcase_01	WA	-
testcase_02	AC	1 ms 5,248 KB
testcase_03	WA	-
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	18 ms 5,248 KB
testcase_08	AC	4 ms 5,248 KB
testcase_09	AC	3 ms 5,248 KB
testcase_10	AC	5 ms 5,248 KB
testcase_11	AC	5 ms 5,248 KB
testcase_12	AC	1 ms 5,248 KB
testcase_13	AC	7 ms 5,248 KB
testcase_14	AC	1 ms 5,248 KB
testcase_15	AC	2 ms 5,248 KB
testcase_16	AC	10 ms 5,248 KB
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	AC	42 ms 5,248 KB
testcase_21	AC	8 ms 5,248 KB
testcase_22	AC	20 ms 5,248 KB
testcase_23	AC	20 ms 5,248 KB
testcase_24	AC	19 ms 5,248 KB
testcase_25	AC	19 ms 5,248 KB
testcase_26	AC	41 ms 5,248 KB
testcase_27	AC	35 ms 5,248 KB
testcase_28	AC	46 ms 5,248 KB
testcase_29	WA	-
testcase_30	WA	-
testcase_31	AC	7 ms 5,248 KB
testcase_32	AC	7 ms 5,248 KB
testcase_33	AC	21 ms 5,248 KB
testcase_34	AC	20 ms 5,248 KB
testcase_35	AC	46 ms 5,248 KB
testcase_36	AC	46 ms 5,248 KB
testcase_37	AC	46 ms 5,248 KB
testcase_38	AC	46 ms 5,248 KB
testcase_39	AC	1 ms 5,248 KB
testcase_40	AC	3 ms 5,248 KB
testcase_41	AC	2 ms 5,248 KB
testcase_42	AC	1 ms 5,248 KB
testcase_43	AC	2 ms 5,248 KB
testcase_44	AC	3 ms 5,248 KB
testcase_45	AC	2 ms 5,248 KB
testcase_46	AC	2 ms 5,248 KB
testcase_47	AC	19 ms 5,248 KB
testcase_48	AC	18 ms 5,248 KB
testcase_49	AC	20 ms 5,248 KB
testcase_50	AC	19 ms 5,248 KB
testcase_51	AC	17 ms 5,248 KB
testcase_52	AC	13 ms 5,248 KB
testcase_53	AC	17 ms 5,248 KB
testcase_54	AC	2 ms 5,248 KB
testcase_55	AC	1 ms 5,248 KB
testcase_56	AC	1 ms 5,248 KB
testcase_57	AC	1 ms 5,248 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#![allow(non_snake_case)]
pub use __cargo_equip::prelude::*;

use proconio::{fastout, input};
use wavelet_matrix::WaveletMatrix;

#[fastout]
fn main() {
    input! {
        N: usize,
        A: [i64; N],
    }
    let sorted_a = {
        let mut a = A.clone();
        a.sort_unstable();
        a.dedup();
        a
    };
    let compressed = A
        .iter()
        .map(|a| sorted_a.binary_search(a).unwrap())
        .collect::<Vec<_>>();
    let wm = WaveletMatrix::new(&compressed);
    let mut ans = 0;
    for k in 1..N {
        let all_teams = N / k;
        let median_id = (k + 1) / 2 - 1;
        let left_sum = {
            let mut left_sum = vec![0; all_teams + 1];
            for i in 0..all_teams {
                // [i * k, (i + 1) * k)
                let left = i * k;
                let right = (i + 1) * k;
                let mid = wm.quantile(left..right, median_id);
                let power = sorted_a[mid] * k as i64;
                left_sum[i + 1] = left_sum[i] + power;
            }
            left_sum
        };
        let right_sum = {
            let mut right_sum = vec![0; all_teams + 1];
            for i in 0..all_teams {
                // [N - (i + 1) * k, N - i * k)
                let left = N - (i + 1) * k;
                let right = N - i * k;
                let mid = wm.quantile(left..right, median_id);
                let power = sorted_a[mid] * k as i64;
                right_sum[i + 1] = right_sum[i] + power;
            }
            right_sum
        };
        debug!(k, all_teams, left_sum, right_sum);
        // 累積Max
        let right_cnt_max = {
            let mut right_cnt_max = right_sum;
            for i in 1..=all_teams {
                right_cnt_max[i] = right_cnt_max[i].max(right_cnt_max[i - 1]);
            }
            right_cnt_max
        };
        for left_cnt in 0..=all_teams {
            let right_cnt = all_teams - left_cnt;
            // [0, right_cnt]の中での最大値
            let power = left_sum[left_cnt] + right_cnt_max[right_cnt];
            ans = ans.max(power);
        }
    }
    println!("{}", ans);
}

/// https://maguro.dev/debug-macro/
#[macro_export]
macro_rules! debug {
    ($($a:expr),* $(,)*) => {
        #[cfg(debug_assertions)]
        eprintln!(concat!($("| ", stringify!($a), "={:?} "),*, "|"), $(&$a),*);
    };
}
// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `bitdict 0.1.0 (path+████████████████████████████████████████████████████████████)`               published in ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__bitdict_0_1_0`
///  - `internal_bits 0.1.0 (path+████████████████████████████████████████████████████████████████████)` published in **missing**                                           licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__internal_bits_0_1_0`
///  - `wavelet_matrix 0.1.0 (path+███████████████████████████████████████████████████████████████████)` published in ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::wavelet_matrix`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod __bitdict_0_1_0 {#[derive(Debug,Clone,Copy)]struct Block{bit:u64,cum_sum_popcnt:u32,}#[derive(Debug,Clone)]pub struct BitDict{len:usize,blocks:Vec<Block>,all_popcnt:usize,one_select:Vec<u32>,zero_select:Vec<u32>,}impl From<&[bool]>for BitDict{fn from(bitvec:&[bool])->Self{let len=bitvec.len();let mut ret=Self::new(len);for(i,&b)in bitvec.iter().enumerate(){if b{ret.set(i);}}ret.build();ret}}impl BitDict{pub fn new(len:usize)->Self{Self{len,blocks:vec![Block{bit:0,cum_sum_popcnt:0};(len>>6)+1],all_popcnt:0,one_select:Vec::new(),zero_select:Vec::new(),}}pub fn rank1_all(&self)->usize{self.all_popcnt}pub fn rank0_all(&self)->usize{self.len-self.all_popcnt}pub fn access(&self,i:usize)->bool{debug_assert!(i<self.len);(self.blocks[i>>6].bit>>(i&63))&1==1}pub fn set(&mut self,i:usize){debug_assert!(i<self.len);self.blocks[i>>6].bit|=1<<(i&63);}pub fn build(&mut self){let all_popcnt=self.blocks.iter().map(|b|b.bit.count_ones()).sum::<u32>()as usize;let mut popcnt=0;let one_num=(all_popcnt>>6)+1;let zero_num=((self.len-all_popcnt)>>6)+1;let mut one_select=Vec::with_capacity(one_num);let mut zero_select=Vec::with_capacity(zero_num);for(i,b)in self.blocks.iter_mut().enumerate(){if popcnt as usize>=one_select.len()<<6{one_select.push(i as u32);}if(i<<6)-popcnt as usize>=zero_select.len()<<6{zero_select.push(i as u32);}b.cum_sum_popcnt=popcnt;popcnt+=b.bit.count_ones();}assert_eq!(popcnt as usize,all_popcnt);self.all_popcnt=all_popcnt;self.one_select=one_select;self.zero_select=zero_select;}pub fn rank_1(&self,i:usize)->usize{debug_assert!(i<=self.len);let Block{bit:block,cum_sum_popcnt,}=self.blocks[i>>6];let mask=(1<<(i&63))-1;let popcnt=(block&mask).count_ones();(cum_sum_popcnt+popcnt)as usize}pub fn rank_0(&self,i:usize)->usize{i-self.rank_1(i)}pub fn select_1(&self,i:usize)->Option<usize>{if i>=self.all_popcnt{return None;}let mut ok=if let Some(&ok)=self.one_select.get(i>>6){ok.saturating_sub(1)as usize}else{self.blocks.len().saturating_sub(1)};let mut ng=if let Some(&ng)=self.one_select.get((i>>6)+1){ng as usize}else{self.blocks.len()};let i=i as u32;while ng-ok>1{let mid=(ok+ng)>>1;if self.blocks[mid].cum_sum_popcnt<=i{ok=mid;}else{ng=mid;}}let rem=i-self.blocks[ok].cum_sum_popcnt;let offset=select1_u64(self.blocks[ok].bit,rem as usize);Some((ok<<6)+offset as usize)}pub fn select_0(&self,i:usize)->Option<usize>{let all_0=self.len-self.all_popcnt;if i>=all_0{return None;}let mut ok=if let Some(&ok)=self.zero_select.get(i>>6){ok.saturating_sub(1)as usize}else{self.blocks.len().saturating_sub(1)};let mut ng=if let Some(&ng)=self.zero_select.get((i>>6)+1){ng as usize}else{self.blocks.len()};while ng-ok>1{let mid=(ok+ng)>>1;if((mid<<6)-self.blocks[mid].cum_sum_popcnt as usize)<=i{ok=mid;}else{ng=mid;}}let rem=i-((ok<<6)-self.blocks[ok].cum_sum_popcnt as usize);let offset=select1_u64(!self.blocks[ok].bit,rem);Some((ok<<6)+offset as usize)}}#[cfg(target_arch="x86_64")]fn select1_u64(x:u64,index:usize)->u32{use std::arch::x86_64::_pdep_u64;let z=1<<index;let y=unsafe{_pdep_u64(z,x)};y.trailing_zeros()}#[cfg(not(target_arch="x86_64"))]fn select1_u64(x:u64,index:usize)->u32{let mut left=0;let mut right=64;while right-left>1{let mid=(left+right)>>1;if(x&((1<<mid)-1)).count_ones()>index as u32{right=mid;}else{left=mid;}}left}}
        pub mod __internal_bits_0_1_0 {pub fn ceil_log2(n:u32)->u32{32-n.saturating_sub(1).leading_zeros()}}
        pub mod wavelet_matrix {use crate::__cargo_equip::preludes::wavelet_matrix::*;use bitdict::BitDict;use internal_bits::ceil_log2;use std::ops::RangeBounds;#[derive(Debug,Clone)]pub struct WaveletMatrix{upper_bound:usize,len:usize,indices:Vec<BitDict>,sorted_positions:Vec<Option<usize>>,counts:Vec<usize>,}impl WaveletMatrix{pub fn new(compressed_list:&[usize])->Self{let len=compressed_list.len();let upper_bound=*compressed_list.iter().max().unwrap_or(&0)+1;let log=ceil_log2(upper_bound as u32+1)as usize;let mut indices=vec![BitDict::new(len);log];let mut tmp=vec![Vec::with_capacity(len);2];let mut list=compressed_list.to_vec();for(ln,index)in indices.iter_mut().enumerate().rev(){for(i,x)in list.drain(..).enumerate(){if(x>>ln)&1==1{index.set(i);tmp[1].push(x);}else{tmp[0].push(x);}}index.build();list.append(&mut tmp[0]);list.append(&mut tmp[1]);}let mut sorted_positions=vec![None;upper_bound+1];let mut counts=vec![0;upper_bound+1];for(i,&x)in list.iter().enumerate(){if sorted_positions[x].is_none(){sorted_positions[x]=Some(i);}counts[x]+=1;}Self{upper_bound,len,indices,sorted_positions,counts,}}pub fn access(&self,mut pos:usize)->usize{assert!(pos<self.len);let mut ret=0;for(ln,index)in self.indices.iter().enumerate().rev(){let bit=index.access(pos);if bit{ret|=1<<ln;pos=index.rank0_all()+index.rank_1(pos);}else{pos=index.rank_0(pos);}}ret}pub fn rank(&self,num:usize,mut pos:usize)->usize{if self.sorted_positions.get(num).unwrap_or(&None).is_none(){return 0;}assert!(pos<=self.len);for(ln,index)in self.indices.iter().enumerate().rev(){let bit=(num>>ln)&1;if bit==1{pos=index.rank0_all()+index.rank_1(pos);}else{pos=index.rank_0(pos);}}pos-self.sorted_positions[num].unwrap()}pub fn rank_less_eq_more<R:RangeBounds<usize>>(&self,num:usize,range:R,)->(usize,usize,usize){let(mut begin,mut end)=self.get_pos_range(range);let range_len=end-begin;if num>=self.upper_bound{return(range_len,0,0);}let mut less=0;let mut more=0;for(ln,index)in self.indices.iter().enumerate().rev(){let bit=(num>>ln)&1;let rank1_begin=index.rank_1(begin);let rank1_end=index.rank_1(end);let rank0_begin=begin-rank1_begin;let rank0_end=end-rank1_end;if bit==1{less+=rank0_end-rank0_begin;begin=index.rank0_all()+rank1_begin;end=index.rank0_all()+rank1_end;}else{more+=rank1_end-rank1_begin;begin=rank0_begin;end=rank0_end;}}let eq=range_len-less-more;(less,eq,more)}pub fn select(&self,num:usize,pos:usize)->Option<usize>{if pos>=*self.counts.get(num)?{return None;}let mut ret=self.sorted_positions[num].unwrap()+pos;for(ln,index)in self.indices.iter().enumerate(){let bit=(num>>ln)&1;if bit==1{ret=index.select_1(ret-index.rank0_all()).unwrap();}else{ret=index.select_0(ret).unwrap();}}Some(ret)}fn get_pos_range<R:RangeBounds<usize>>(&self,range:R)->(usize,usize){use std::ops::Bound::*;let left=match range.start_bound(){Included(&x)=>x,Excluded(&x)=>x+1,Unbounded=>0,};let right=match range.end_bound(){Included(&x)=>x+1,Excluded(&x)=>x,Unbounded=>self.len,};assert!(left<=right&&right<=self.len);(left,right)}pub fn quantile<R:RangeBounds<usize>>(&self,range:R,mut k:usize)->usize{let(mut begin,mut end)=self.get_pos_range(range);assert!(k<end-begin);let mut ret=0;for(ln,index)in self.indices.iter().enumerate().rev(){let one_cnt=index.rank_1(end)-index.rank_1(begin);let zero_cnt=end-begin-one_cnt;if k<zero_cnt{begin=index.rank_0(begin);end=index.rank_0(end);}else{ret|=1<<ln;k-=zero_cnt;begin=index.rank0_all()+index.rank_1(begin);end=index.rank0_all()+index.rank_1(end);}}ret}fn get_num_range<R:RangeBounds<usize>>(&self,range:R)->(usize,usize){use std::ops::Bound::*;let left=match range.start_bound(){Included(&x)=>x,Excluded(&x)=>x+1,Unbounded=>0,}.min(self.upper_bound);let right=match range.end_bound(){Included(&x)=>x+1,Excluded(&x)=>x,Unbounded=>self.upper_bound,}.min(self.upper_bound);assert!(left<=right);(left,right)}pub fn range_freq<R1:RangeBounds<usize>+Clone,R2:RangeBounds<usize>>(&self,pos_range:R1,num_range:R2,)->usize{let(num_begin,num_end)=self.get_num_range(num_range);if num_begin>=num_end{return 0;}let cnt_begin=self.rank_less_eq_more(num_begin,pos_range.clone()).0;let cnt_end=self.rank_less_eq_more(num_end,pos_range).0;cnt_end-cnt_begin}pub fn next_value<R:RangeBounds<usize>+Clone>(&self,range:R,lower:usize,)->Option<usize>{let(less,eq,upper)=self.rank_less_eq_more(lower,range.clone());if eq>0{return Some(lower);}if upper==0{return None;}Some(self.quantile(range,less))}pub fn prev_value<R:RangeBounds<usize>+Clone>(&self,range:R,upper:usize,)->Option<usize>{let less=self.rank_less_eq_more(upper,range.clone()).0;if less==0{return None;}Some(self.quantile(range,less-1))}}}
    }

    pub(crate) mod macros {
        pub mod __bitdict_0_1_0 {}
        pub mod __internal_bits_0_1_0 {}
        pub mod wavelet_matrix {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod __bitdict_0_1_0 {}
        pub mod __internal_bits_0_1_0 {}
        pub mod wavelet_matrix {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__bitdict_0_1_0 as bitdict,__internal_bits_0_1_0 as internal_bits};}
    }
}

yukicoder

結果

テストケース

ソースコード