結果
| 問題 |
No.1917 LCMST
|
| コンテスト | |
| ユーザー |
 rhoo
|
| 提出日時 | 2025-07-16 10:24:54 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 10,260 bytes |
| コンパイル時間 | 12,552 ms |
| コンパイル使用メモリ | 398,560 KB |
| 実行使用メモリ | 812,928 KB |
| 最終ジャッジ日時 | 2025-07-16 10:27:05 |
| 合計ジャッジ時間 | 112,601 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 32 TLE * 1 MLE * 8 -- * 1 |
ソースコード
#![allow(unused_imports,non_snake_case,dead_code)]
use std::{cmp::Reverse as Rev,ops::Range,collections::*,iter::*};
use proconio::{marker::*,*};
// LCMST
type HashMap<K,V>=rustc_hash::FxHashMap<K,V>;
#[fastout]
fn main(){
input!{
n:usize,
a:[usize;n],
}
let mut era=vec![!0;1e6 as usize+5];
for i in 2..era.len(){
if era[i]!=!0{
continue;
}
for j in 1..{
if era.len()<=i*j{
break;
}
era[i*j]=i;
}
}
let divisor=|mut n:usize|->Vec<usize>{
let mut ps=vec![];
while era[n]!=!0{
let p=era[n];
let mut cnt=0;
while n%p==0{
cnt+=1;
n/=p;
}
ps.push((p,cnt));
}
if n!=1{
ps.push((n,1));
}
fn rec(ps:&[(usize,usize)],i:usize,mut div:usize,divs:&mut Vec<usize>){
if i==!0{
divs.push(div);
return;
}
let (p,cnt)=ps[i];
for _ in 0..=cnt{
rec(ps,i-1,div,divs);
div*=p;
}
}
let mut divs=vec![];
rec(&ps,ps.len()-1,1,&mut divs);
divs
};
let divs=(0..n).map(|i|divisor(a[i])).collect::<Vec<_>>();
let mut id_to_div=divs.iter().flatten().copied().collect::<Vec<_>>();
id_to_div.sort_unstable();
id_to_div.dedup();
let mut div_to_id=HashMap::default();
for i in 0..id_to_div.len(){
div_to_id.insert(id_to_div[i],i);
}
let mut div_set=vec![vec![];id_to_div.len()];
for i in 0..n{
for &d in &divs[i]{
let id=div_to_id[&d];
div_set[id].push(a[i]);
}
}
for i in 0..div_set.len(){
div_set[i].sort_unstable_by_key(|&t|!t);
}
// type MultiSet=BTreeMap<usize,usize>;
// fn add(set:&mut MultiSet,a:usize){
// *set.entry(a).or_insert(0)+=1;
// }
// fn rem(set:&mut MultiSet,a:usize){
// let e=set.get_mut(&a).unwrap();
// *e-=1;
// if *e==0{
// set.remove(&a);
// }
// }
#[derive(Clone,Debug)]
struct Queue{
d:usize,
que:usize,
co_que:Vec<usize>,
w:usize,
}
let init_que=|d:usize|{
let id=div_to_id[&d];
Queue{
d,
que:!0,
co_que:div_set[id].clone(),
w:!0,
}
};
let mut cnt=vec![0;1e6 as usize+5];
for i in 0..n{
cnt[a[i]]+=1;
}
let mut que=id_to_div.iter().map(|&d|init_que(d)).collect::<Vec<Queue>>();
let mut min=BTreeSet::new();
cap!{
#![&a:[usize],&mut que:[Queue],&divs:[Vec<usize>],&div_to_id:rustc_hash::FxHashMap<usize,usize>,
&mut min:BTreeSet<(usize,usize)>,&mut cnt:[usize]]
// a[i]をprimとして確定させる
fn mov(i:usize){
cnt[a[i]]-=1;
for &n in &divs[i]{
let id=div_to_id[&n];
let que=&mut que[id];
if que.w!=!0{
min.remove(&(que.w,que.d));
}
que.que=que.que.min(a[i]);
while let Some(&v)=que.co_que.last(){
if cnt[v]==0{
que.co_que.pop().unwrap();
} else{
break;
}
}
if que.que!=!0 && !que.co_que.is_empty(){
let m0=que.que;
let m1=que.co_que.last().unwrap();
que.w=m0/que.d*m1;
min.insert((que.w,que.d));
} else{
que.w=!0;
}
}
}
}
let mut index=HashMap::default();
for i in 0..n{
index.entry(a[i]).or_insert(vec![]).push(i);
}
mov!(0);
let mut ans=0;
for _ in 1..n{
let (w,d)=min.first().unwrap();
ans+=w;
let id=div_to_id[&d];
let new=*que[id].co_que.last().unwrap();
let idx=index.get_mut(&new).unwrap().pop().unwrap();
mov!(idx);
}
println!("{ans}");
}
#[macro_export]
macro_rules! cap{
()=>{};
(#![] $($fn:tt)*)=>{
cap!([],[],[],[],[$($fn)*],[],[]);
};
(#![$($g:tt)*] $($fn:tt)*)=>{
cap!([$($g)*,],[],[],[],[$($fn)*],[],[]);
};
([$name:ident:$t:ty,$($rem:tt)*],[$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[$($fn:tt)*],[],[])=>{
cap!([$($rem)*],[$name:$t,$($ga)*],[$name,$($gn)*],[$name,$($ge)*],[$($fn)*],[],[]);
};
([$($flag:tt)? $name:ident:$t:ty,$($rem:tt)*],[$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[$($fn:tt)*],[],[])=>{
cap!([$($rem)*],[$name:$($flag)?$t,$($ga)*],[$name,$($gn)*],[$($flag)?$name,$($ge)*],[$($fn)*],[],[]);
};
([&mut $name:ident:$t:ty,$($rem:tt)*],[$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[$($fn:tt)*],[],[])=>{
cap!([$($rem)*],[$name:&mut $t,$($ga)*],[$name,$($gn)*],[&mut $name,$($ge)*],[$($fn)*],[],[]);
};
([],[$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[$(#[$($att:tt)*])? fn $name:ident($($arg:tt)*) $body:block $($rem:tt)*],[$($info:tt)*],[$($fn:tt)*])=>{
cap!([],[$($ga)*],[$($gn)*],[$($ge)*],[$($rem)*],[(($(#[$($att)*])?),$name,($($arg)*),(),$body),$($info)*],[$name,$($fn)*]);
};
([],[$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[$(#[$($att:tt)*])? fn $name:ident($($arg:tt)*)->$ret:ty $body:block $($rem:tt)*],[$($info:tt)*],[$($fn:tt)*])=>{
cap!([],[$($ga)*],[$($gn)*],[$($ge)*],[$($rem)*],[(($(#[$($att)*])?),$name,($($arg)*),$ret,$body),$($info)*],[$name,$($fn)*]);
};
([],[$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[],[$($info:tt)*],[$($fn:tt)*])=>{
cap!(@make_fn [$($ga)*],[$($gn)*],[$($ge)*],[$($info)*],[$($fn)*]);
};
(@make_fn [$($ga:ident:$gt:ty,)*],[$($gn:tt)*],[$($ge:tt)*],[(($($att:tt)*),$name:ident,($($arg:tt)*),$ret:ty,$body:block),$($rem:tt)*],[$($fn:tt)*])=>{
$($att)*
fn $name($($ga:$gt,)*$($arg)*)->$ret{
$(#[allow(unused_variables)] let $ga=$ga;)*
cap!(@make_macros ($),[$($gn)*],[$($fn)*]);
$body
}
cap!(@make_fn [$($ga:$gt,)*],[$($gn)*],[$($ge)*],[$($rem)*],[$($fn)*]);
};
(@make_fn [$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[],[$($fn:tt)*])=>{
cap!(@make_global_macros ($),[$($ge)*],[$($fn)*]);
};
(@make_macros ($dol:tt),[$($gn:ident,)*],[$name:ident,$($rem:tt)*])=>{
#[allow(unused_macros)]
macro_rules! $name{
($dol($dol arg:expr),*)=>{$name($($gn,)* $dol($dol arg),*)}
}
cap!(@make_macros ($),[$($gn,)*],[$($rem)*]);
};
(@make_macros ($dol:tt),[$($gn:ident,)*],[])=>{};
(@make_global_macros ($dol:tt),[$($ge:expr,)*],[$name:ident,$($rem:tt)*])=>{
#[allow(unused_macros)]
macro_rules! $name{
($dol($dol arg:expr),*)=>{$name($($ge,)* $dol($dol arg),*)}
}
cap!(@make_global_macros ($),[$($ge,)*],[$($rem)*]);
};
(@make_global_macros ($dol:tt),[$($ge:expr,)*],[])=>{};
}
mod rustc_hash{
use core::convert::TryInto;
use core::default::Default;
use core::hash::BuildHasherDefault;
use core::hash::Hasher;
use core::mem::size_of;
use core::ops::BitXor;
use std::collections::{HashMap, HashSet};
pub type FxHashMap<K, V> = HashMap<K, V, BuildHasherDefault<FxHasher>>;
pub type FxHashSet<V> = HashSet<V, BuildHasherDefault<FxHasher>>;
pub struct FxHasher {
hash: usize,
}
#[cfg(target_pointer_width = "32")]
const K: usize = 0x9e3779b9;
#[cfg(target_pointer_width = "64")]
const K: usize = 0x517cc1b727220a95;
impl Default for FxHasher {
#[inline]
fn default() -> FxHasher {
FxHasher { hash: 0 }
}
}
impl FxHasher {
#[inline]
fn add_to_hash(&mut self, i: usize) {
self.hash = self.hash.rotate_left(5).bitxor(i).wrapping_mul(K);
}
}
impl Hasher for FxHasher {
#[inline]
fn write(&mut self, mut bytes: &[u8]) {
#[cfg(target_pointer_width = "32")]
let read_usize = |bytes: &[u8]| u32::from_ne_bytes(bytes[..4].try_into().unwrap());
#[cfg(target_pointer_width = "64")]
let read_usize = |bytes: &[u8]| u64::from_ne_bytes(bytes[..8].try_into().unwrap());
let mut hash = FxHasher { hash: self.hash };
assert!(size_of::<usize>() <= 8);
while bytes.len() >= size_of::<usize>() {
hash.add_to_hash(read_usize(bytes) as usize);
bytes = &bytes[size_of::<usize>()..];
}
if (size_of::<usize>() > 4) && (bytes.len() >= 4) {
hash.add_to_hash(u32::from_ne_bytes(bytes[..4].try_into().unwrap()) as usize);
bytes = &bytes[4..];
}
if (size_of::<usize>() > 2) && bytes.len() >= 2 {
hash.add_to_hash(u16::from_ne_bytes(bytes[..2].try_into().unwrap()) as usize);
bytes = &bytes[2..];
}
if (size_of::<usize>() > 1) && bytes.len() >= 1 {
hash.add_to_hash(bytes[0] as usize);
}
self.hash = hash.hash;
}
#[inline]
fn write_u8(&mut self, i: u8) {
self.add_to_hash(i as usize);
}
#[inline]
fn write_u16(&mut self, i: u16) {
self.add_to_hash(i as usize);
}
#[inline]
fn write_u32(&mut self, i: u32) {
self.add_to_hash(i as usize);
}
#[cfg(target_pointer_width = "32")]
#[inline]
fn write_u64(&mut self, i: u64) {
self.add_to_hash(i as usize);
self.add_to_hash((i >> 32) as usize);
}
#[cfg(target_pointer_width = "64")]
#[inline]
fn write_u64(&mut self, i: u64) {
self.add_to_hash(i as usize);
}
#[inline]
fn write_usize(&mut self, i: usize) {
self.add_to_hash(i);
}
#[inline]
fn finish(&self) -> u64 {
self.hash as u64
}
}
}