結果
| 問題 | No.5011 Better Mo's Algorithm is Needed!! (Weighted) |
| ユーザー |
 rhoo
|
| 提出日時 | 2022-12-18 00:50:45 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,850 bytes |
| コンパイル時間 | 4,335 ms |
| 実行使用メモリ | 31,924 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2022-12-18 00:51:24 |
| 合計ジャッジ時間 | 30,648 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
| testcase_87 | -- | - |
| testcase_88 | -- | - |
| testcase_89 | -- | - |
| testcase_90 | -- | - |
| testcase_91 | -- | - |
| testcase_92 | -- | - |
| testcase_93 | -- | - |
| testcase_94 | -- | - |
| testcase_95 | -- | - |
| testcase_96 | -- | - |
| testcase_97 | -- | - |
| testcase_98 | -- | - |
| testcase_99 | -- | - |
| testcase_100 | -- | - |
| testcase_101 | -- | - |
| testcase_102 | -- | - |
| testcase_103 | -- | - |
| testcase_104 | -- | - |
| testcase_105 | -- | - |
| testcase_106 | -- | - |
| testcase_107 | -- | - |
| testcase_108 | -- | - |
| testcase_109 | -- | - |
| testcase_110 | -- | - |
| testcase_111 | -- | - |
| testcase_112 | -- | - |
| testcase_113 | -- | - |
| testcase_114 | -- | - |
| testcase_115 | -- | - |
| testcase_116 | -- | - |
| testcase_117 | -- | - |
| testcase_118 | -- | - |
| testcase_119 | -- | - |
コンパイルメッセージ
warning: unused macro definition: `debug`
--> Main.rs:88:14
|
88 | macro_rules! debug{
| ^^^^^
|
= note: `#[warn(unused_macros)]` on by default
warning: unused macro definition: `param`
--> Main.rs:152:14
|
152 | macro_rules! param{
| ^^^^^
warning: unused import: `std::mem`
--> Main.rs:203:5
|
203 | use std::mem;
| ^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: function is never used: `abs_diff`
--> Main.rs:223:4
|
223 | fn abs_diff(a:usize,b:usize)->usize{
| ^^^^^^^^
|
= note: `#[warn(dead_code)]` on by default
warning: field is never read: `wt`
--> Main.rs:229:5
|
229 | wt:usize,
| ^^^^^^^^
warning: field is never read: `st`
--> Main.rs:230:5
|
230 | st:usize,
| ^^^^^^^^
warning: associated function is never used: `score`
--> Main.rs:311:8
|
311 | fn score(&self)->i64{
| ^^^^^
warning: 7 warnings emitted
ソースコード
#![allow(non_snake_case)]
#[allow(unused)]
mod rnd {
static mut S:usize=88172645463325252;
#[inline]
pub fn next()->usize{
unsafe{
S^=S<<7;
S^=S>>9;
S
}
}
#[inline]
pub fn nextf()->f64{
unsafe{
std::mem::transmute::<_,f64>(0x3ff0000000000000|next()&0xfffffffffffff)-1.
}
}
#[inline]
pub fn range(a:usize,b:usize)->usize{
next()%(b-a)+a
}
#[inline]
pub fn exu(a:usize,b:usize,skip:usize)->usize{
let ret=range(a,b-1);
if ret==skip{b-1}
else{ret}
}
#[inline]
pub fn shuffle<T>(list:&mut [T]){
for i in (0..list.len()).rev(){
list.swap(i,next()%(i+1));
}
}
}
#[inline]
fn get_time_secs()->f64{
std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_secs_f64()
}
struct Timer(f64);
impl Timer{
#[inline]
fn new()->Timer{
Timer(get_time_secs())
}
#[inline]
fn get_time(&self)->f64{
get_time_secs()-self.0
}
}
#[cfg(local)]
#[allow(unused)]
macro_rules! debug{
()=>{
eprintln!();
};
($x:literal)=>{
eprintln!("{:?}",$x);
};
($x:expr)=>{
eprintln!("{}: {:?}",stringify!($x),$x);
};
($x:literal,$($l:expr),*)=>{
eprint!("{:?}, ",$x);
debug!($($l),*);
};
($x:expr,$($l:expr),*)=>{
eprint!("{}: {:?}, ",stringify!($x),$x);
debug!($($l),*);
}
}
#[cfg(not(local))]
macro_rules! debug{
($($_:tt)*)=>{}
}
#[cfg(local)]
macro_rules! log{
()=>{};
($x:literal)=>{
eprintln!("{}",$x);
};
($x:ident $(,)?)=>{
log!(@out $x,$x);
};
($x:ident,$t:ident $(,)?)=>{
log!(@out $x,$x);
log!($t);
};
($x:ident,$($_:ident).* $(,)?)=>{
compile_error!();
};
($x:ident,$t:expr $(,)?)=>{
log!(@out $x,$t);
};
($($x:ident).* $(,)?)=>{
log!(@last $($x).*;$($x).*);
};
($x:ident,$t:ident,$($rest:tt)*)=>{
log!(@out $x,$x);
log!($t,$($rest)*);
};
($x:ident,$($_:ident).*,$($rest:tt)*)=>{
compile_error!();
};
($x:ident,$t:expr,$($rest:tt)*)=>{
log!(@out $x,$t);
log!($($rest)*);
};
($($x:ident).*,$($rest:tt)*)=>{
log!(@last $($x).*;$($x).*);
log!($($rest)*);
};
(@out $x:ident,$t:expr)=>{
eprintln!("{} = {:?}",stringify!($x),$t);
};
(@last $x:ident;$full:expr)=>{
log!(@out $x,$full);
};
(@last $_:ident. $($rest:ident).*;$full:expr)=>{
log!(@last $($rest).*;$full)
}
}
#[cfg(not(local))]
macro_rules! log{
($($_:tt)*)=>{}
}
macro_rules! param{
($($x:ident:$t:ty=$v:literal),* $(,)?)=>{
#[allow(non_snake_case)]
struct Param{
$($x:$t),*
}
impl Param{
#[inline]
fn new()->Self{
Self{
$(
$x:match std::env::var(stringify!($x)){
Ok(s)=>s.parse().expect("parse error"),
Err(_)=>$v
}
),*
}
}
}
};
}
#[allow(unused)]
struct Scanner{
stack:std::str::SplitAsciiWhitespace<'static>
}
#[allow(unused)]
impl Scanner{
#[inline]
fn new()->Self{
Self{stack:"".split_ascii_whitespace()}
}
#[inline]
fn read<T:std::str::FromStr>(&mut self)->T{
loop{
if let Some(v)=self.stack.next(){
return v.parse::<T>().unwrap_or_else(|_|panic!("{}: parse error",std::any::type_name::<T>()));
}
let mut tmp=String::new();
std::io::stdin().read_line(&mut tmp).unwrap();
assert!(!tmp.is_empty());
self.stack=Box::leak(tmp.into_boxed_str()).split_ascii_whitespace();
}
}
}
use std::io::*;
use std::mem;
use std::cmp::Reverse;
const N:usize=200000;
const Q:usize=200000;
#[inline]
fn min_max(a:usize,b:usize)->(usize,usize){
if a>b{
(b,a)
}
else{
(a,b)
}
}
#[inline]
fn abs_diff(a:usize,b:usize)->usize{
(a as i64-b as i64).abs() as usize
}
struct Out{
wt:usize,
st:usize,
sum:Vec<usize>,
route:Vec<(usize,usize,usize)>
}
impl Out{
#[inline]
fn input()->Out{
let mut scan=Scanner::new();
let n:usize=scan.read();
let q:usize=scan.read();
let wt:usize=scan.read();
let st:usize=scan.read();
assert_eq!((n,q),(N,Q));
let mut sum=Vec::with_capacity(N);
sum.push(0);
for _ in 0..n{
let v:usize=scan.read();
sum.push(sum.last().unwrap().clone()+v);
}
let mut route=Vec::with_capacity(Q);
for i in 0..Q{
let l:usize=scan.read();
let r=scan.read::<usize>()-1;
route.push((l,r,i));
}
Out{wt,sum,st,route}
}
#[inline]
fn greedy(&mut self){
const D:usize=15;
self.route[1..].sort_unstable();
let mut block0=vec![Vec::with_capacity(Q/D);D];
let w=Q/D;
for i in 0..Q{
block0[(i/w).min(D-1)].push(self.route[i]);
}
let mut block1=vec![vec![Vec::with_capacity(Q/(D*D));D];D];
for i in 0..D{
block0[i].sort_unstable_by_key(|(_,r,_)|*r);
let w=block0[i].len()/D;
for j in 0..block0[i].len(){
block1[i][(j/w).min(D-1)].push(block0[i][j]);
}
}
let mut blocks=Vec::with_capacity(D*D);
for (i,b0) in block1.into_iter().enumerate(){
for (j,b1) in b0.into_iter().enumerate(){
blocks.push((i,j,b1));
}
}
blocks.sort_unstable_by_key(|&(y,x,_)|{
if D&1!=y&1{
Reverse((y,!x))
}
else{
Reverse((y,x))
}
});
self.route.clear();
for (_,_,mut block) in blocks{
while !block.is_empty(){
let arg_max=if self.route.is_empty(){
(0..block.len()).min_by_key(|&i|self.get_first(block[i])).unwrap()
}
else{
let last=self.route.last().unwrap().clone();
(0..block.len()).min_by_key(|&i|self.get(last,block[i])).unwrap()
};
self.route.push(block.swap_remove(arg_max));
}
}
assert_eq!(self.route.len(),Q);
}
#[inline]
fn score(&self)->i64{
let mut ret=self.get_first(self.route[0]);
for i in 1..self.route.len(){
ret+=self.dist(i-1,i);
}
ret as i64
}
#[inline]
fn get_first(&self,(l,r,_):(usize,usize,usize))->usize{
self.sum[l]-self.sum[r]
}
#[inline]
fn get(&self,(l0,r0,_):(usize,usize,usize),(l1,r1,_):(usize,usize,usize))->usize{
let (l0,l1)=min_max(l0,l1);
let (r0,r1)=min_max(r0,r1);
self.sum[l1]-self.sum[l0]+self.sum[r1]-self.sum[r0]
}
#[inline]
fn dist(&self,a:usize,b:usize)->usize{
self.get(self.route[a],self.route[b])
}
#[inline]
fn try_2opt(&self,a:usize,b:usize)->i64{
let old=self.dist(a-1,a)+self.dist(b-1,b);
let new=self.dist(a-1,b-1)+self.dist(a,b);
(new-old) as i64
}
#[inline]
fn apply_2opt(&mut self,a:usize,b:usize){
self.route[a..b].reverse()
}
}
const TL:f64=4.98;
fn hc(out:&mut Out,d:usize){
for a in 1..Q-d{
for b in a+2..a+d{
let diff=out.try_2opt(a,b);
if diff<=0{
out.apply_2opt(a,b);
}
}
}
log!(score,out.score() as f64/5e7);
}
fn hc_with_timer(out:&mut Out,time:&Timer,d:usize){
let mut iter=0;
for a in 1..Q-d{
for b in a+2..a+d{
if iter&255==0 && time.get_time()>=TL{
return;
}
iter+=1;
let diff=out.try_2opt(a,b);
if diff<=0{
out.apply_2opt(a,b);
}
}
}
log!(score,out.score() as f64/5e7);
}
fn main(){
let time=Timer::new();
let mut out=Out::input();
out.greedy();
log!(init_score,out.score() as f64/5e7);
hc(&mut out,1200);
hc(&mut out,1200);
hc(&mut out,600);
hc(&mut out,600);
hc_with_timer(&mut out,&time,300);
hc_with_timer(&mut out,&time,300);
hc_with_timer(&mut out,&time,300);
hc_with_timer(&mut out,&time,500);
let stdout=stdout();
let stdout=&mut BufWriter::new(stdout.lock());
for (_,_,id) in &out.route{
writeln!(stdout,"{}",id+1).unwrap();
}
stdout.flush().unwrap();
}