#721440 (Rust) No.5004 Room Assignment

提出ソース

結果

問題	No.5004 Room Assignment
ユーザー	ts_
提出日時	2021-12-03 02:25:57
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	152 ms / 5,000 ms
コード長	11,136 bytes
コンパイル時間	2,576 ms
実行使用メモリ	22,392 KB
スコア	138,744,239
平均クエリ数	7617.97
最終ジャッジ日時	2021-12-03 02:26:22
合計ジャッジ時間	24,380 ms
ジャッジサーバーID （参考情報）	judge14 / judge13
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	140 ms 22,104 KB
testcase_01	AC	139 ms 21,960 KB
testcase_02	AC	139 ms 22,028 KB
testcase_03	AC	141 ms 21,936 KB
testcase_04	AC	138 ms 21,960 KB
testcase_05	AC	138 ms 22,092 KB
testcase_06	AC	139 ms 21,996 KB
testcase_07	AC	139 ms 21,780 KB
testcase_08	AC	140 ms 22,080 KB
testcase_09	AC	139 ms 21,912 KB
testcase_10	AC	138 ms 21,984 KB
testcase_11	AC	138 ms 22,356 KB
testcase_12	AC	141 ms 22,164 KB
testcase_13	AC	143 ms 21,980 KB
testcase_14	AC	138 ms 21,984 KB
testcase_15	AC	140 ms 22,092 KB
testcase_16	AC	139 ms 21,900 KB
testcase_17	AC	139 ms 21,972 KB
testcase_18	AC	138 ms 22,080 KB
testcase_19	AC	139 ms 22,116 KB
testcase_20	AC	138 ms 22,140 KB
testcase_21	AC	138 ms 21,984 KB
testcase_22	AC	138 ms 21,972 KB
testcase_23	AC	138 ms 22,224 KB
testcase_24	AC	143 ms 22,116 KB
testcase_25	AC	139 ms 21,900 KB
testcase_26	AC	141 ms 21,948 KB
testcase_27	AC	140 ms 21,960 KB
testcase_28	AC	139 ms 22,164 KB
testcase_29	AC	139 ms 22,164 KB
testcase_30	AC	141 ms 21,972 KB
testcase_31	AC	138 ms 21,900 KB
testcase_32	AC	141 ms 21,948 KB
testcase_33	AC	140 ms 22,128 KB
testcase_34	AC	138 ms 22,356 KB
testcase_35	AC	139 ms 21,960 KB
testcase_36	AC	139 ms 22,140 KB
testcase_37	AC	139 ms 22,152 KB
testcase_38	AC	139 ms 22,212 KB
testcase_39	AC	140 ms 21,804 KB
testcase_40	AC	140 ms 21,948 KB
testcase_41	AC	143 ms 21,948 KB
testcase_42	AC	138 ms 22,020 KB
testcase_43	AC	140 ms 21,960 KB
testcase_44	AC	138 ms 21,924 KB
testcase_45	AC	140 ms 22,052 KB
testcase_46	AC	139 ms 21,900 KB
testcase_47	AC	139 ms 22,128 KB
testcase_48	AC	139 ms 22,104 KB
testcase_49	AC	139 ms 21,900 KB
testcase_50	AC	141 ms 21,948 KB
testcase_51	AC	140 ms 21,912 KB
testcase_52	AC	137 ms 21,888 KB
testcase_53	AC	138 ms 22,032 KB
testcase_54	AC	141 ms 21,900 KB
testcase_55	AC	139 ms 22,140 KB
testcase_56	AC	139 ms 21,936 KB
testcase_57	AC	141 ms 22,092 KB
testcase_58	AC	138 ms 22,104 KB
testcase_59	AC	138 ms 21,888 KB
testcase_60	AC	137 ms 21,936 KB
testcase_61	AC	138 ms 21,768 KB
testcase_62	AC	139 ms 21,948 KB
testcase_63	AC	139 ms 21,960 KB
testcase_64	AC	137 ms 22,392 KB
testcase_65	AC	141 ms 22,044 KB
testcase_66	AC	141 ms 21,900 KB
testcase_67	AC	138 ms 21,888 KB
testcase_68	AC	140 ms 21,780 KB
testcase_69	AC	139 ms 22,152 KB
testcase_70	AC	138 ms 22,140 KB
testcase_71	AC	139 ms 22,092 KB
testcase_72	AC	138 ms 22,032 KB
testcase_73	AC	137 ms 21,948 KB
testcase_74	AC	152 ms 21,840 KB
testcase_75	AC	145 ms 21,780 KB
testcase_76	AC	139 ms 21,984 KB
testcase_77	AC	139 ms 21,792 KB
testcase_78	AC	139 ms 22,092 KB
testcase_79	AC	139 ms 22,152 KB
testcase_80	AC	138 ms 22,104 KB
testcase_81	AC	140 ms 21,948 KB
testcase_82	AC	140 ms 21,924 KB
testcase_83	AC	141 ms 21,888 KB
testcase_84	AC	141 ms 22,236 KB
testcase_85	AC	139 ms 21,992 KB
testcase_86	AC	139 ms 22,188 KB
testcase_87	AC	140 ms 21,972 KB
testcase_88	AC	142 ms 21,792 KB
testcase_89	AC	138 ms 21,768 KB
testcase_90	AC	139 ms 21,924 KB
testcase_91	AC	140 ms 22,092 KB
testcase_92	AC	138 ms 22,080 KB
testcase_93	AC	140 ms 21,936 KB
testcase_94	AC	139 ms 21,972 KB
testcase_95	AC	138 ms 21,780 KB
testcase_96	AC	139 ms 22,116 KB
testcase_97	AC	140 ms 21,984 KB
testcase_98	AC	139 ms 21,924 KB
testcase_99	AC	140 ms 22,044 KB

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

ソースコード

raw source code

#![allow(unused_imports)]
#![allow(dead_code)]
#![allow(unused_macros)]

use std::{collections::{VecDeque, HashSet}, io::{StdoutLock, prelude::*}, writeln};
use std::io::{BufWriter};
 
pub fn readln() -> String {
	let mut line = String::new();
	::std::io::stdin().read_line(&mut line).unwrap_or_else(|e| panic!("{}", e));
	line
}
 
macro_rules! read {
	($($t:tt),*; $n:expr) => {{
		let stdin = ::std::io::stdin();
		let ret = ::std::io::BufRead::lines(stdin.lock()).take($n).map(|line| {
			let line = line.unwrap();
			let mut it = line.split_whitespace();
			_read!(it; $($t),*)
		}).collect::<Vec<_>>();
		ret
	}};
	($($t:tt),*) => {{
		let line = readln();
		let mut it = line.split_whitespace();
		_read!(it; $($t),*)
	}};
}
 
macro_rules! _read {
	($it:ident; [char]) => {
		_read!($it; String).chars().collect::<Vec<_>>()
	};
	($it:ident; [u8]) => {
		Vec::from(_read!($it; String).into_bytes())
	};
	($it:ident; usize1) => {
        $it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1
	};
	($it:ident; [usize1]) => {
		$it.map(|s| s.parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1).collect::<Vec<_>>()
	};
	($it:ident; [$t:ty]) => {
		$it.map(|s| s.parse::<$t>().unwrap_or_else(|e| panic!("{}", e))).collect::<Vec<_>>()
	};
	($it:ident; $t:ty) => {
		$it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<$t>().unwrap_or_else(|e| panic!("{}", e))
	};
	($it:ident; $($t:tt),+) => {
		($(_read!($it; $t)),*)
	};
}

const T: usize = 3600;
const B: usize = 200;
const INF: usize = 1000000007;
const V: [usize; 5] = [0, 0, 1, 3, 6];

struct Room {
    s_max: usize,
    s_min: usize,
    ticks: Vec<usize>,
    cost: usize,
    score: usize,
    player_sk: Vec<usize>,
    player_id: Vec<usize>,
    used: bool,
}

fn calc_score(room: &Room, t: usize, s: usize) -> usize {
    let mut e = 0;
    let n = room.ticks.len();
    for i in 0..n {
        e += t - room.ticks[i];
    }
    let mn = room.s_min.min(s);
    let mx = room.s_max.max(s);
    (V[n+1] * (B.saturating_sub((mx - mn) * (mx - mn)))).saturating_sub(e+room.cost)
}

fn calc_score2(room1: &Room, room2: &Room, t: usize) -> usize {
    let mut e = 0;
    let n1 = room1.ticks.len();
    let n2 = room2.ticks.len();
    for i in 0..n2 {
        e += (t - room2.ticks[i])*2;
    }
    for i in 0..n1 {
        e += (t - room1.ticks[i])*2;
    }
    let mn = room1.s_min.min(room2.s_min);
    let mx = room1.s_max.max(room2.s_max);
    (V[4] * (B.saturating_sub((mx - mn) * (mx - mn)))).saturating_sub(e+room1.cost+room2.cost)
}

fn main() {
    
    //let mut buffer = String::new();
    //std::io::stdin().read_to_string(&mut buffer).unwrap();
    //let mut input = buffer.split_whitespace();
    /*
    input!{
        input,
        n: usize,
        mut a: [usize; n]
    }
    */
    let stdout = std::io::stdout();
    let mut stdout = BufWriter::new(stdout.lock());

    let (_, _) = read!(usize, usize);
    let mut rooms: Vec<Room> = Vec::new();
    let mut num_player = 0;
    //let mut rem = HashSet::new();
    for ti in 0..T {
        //let n = read!(usize);
        let sv = readln();
        let sv: Vec<&str> = sv.split_whitespace().collect();
        let n = sv[0].parse::<usize>().unwrap();
        let mut ret: Vec<(usize, usize)> = vec![];
        for ii in 0..n {
            num_player += 1;
            let si = sv[ii+1].parse::<usize>().unwrap();
            let mut mx = 100;
            let mut room_id = INF;
            for (id, ri) in rooms.iter().enumerate() {
                if ri.ticks.len() == 4 || ri.used {continue;}
                let tmp_score = calc_score(ri, ti, si);
                let sp = ri.s_max.max(si) - ri.s_min.min(si);
                if mx < tmp_score && sp < 4 {
                    mx = tmp_score;
                    room_id = id;
                }
                
            }
            if room_id < INF {
                let mut co = 0;
                for &tti in rooms[room_id].ticks.iter() {
                    co += ti - tti;
                }
                //mx = calc_score(&rooms[room_id], ti, si);
                ret.push((num_player, rooms[room_id].player_id[0]));
                rooms[room_id].player_id.push(num_player);
                rooms[room_id].s_max = rooms[room_id].s_max.max(si);
                rooms[room_id].s_min = rooms[room_id].s_min.min(si);
                rooms[room_id].score = mx;
                rooms[room_id].ticks.push(ti);
                rooms[room_id].player_sk.push(si);
                rooms[room_id].cost += co;
            }
            else {
                rooms.push(Room{s_max: si, s_min: si, ticks: vec![ti], score: 0, player_id: vec![num_player], player_sk: vec![si], cost: 0, used: false});
            }
        }
        
        if (ti+1) % 18 == 0 {
            let r = rooms.len().min(20);
            let rn = rooms.len();
            for r1 in rn-r..rn {
                if rooms[r1].used || rooms[r1].ticks.len() != 2 {continue;}
                let mut mx = 800;
                let mut room_id = INF;
                for r2 in rn-r..rn {
                    if rooms[r2].used || rooms[r2].ticks.len() != 2 || r1 == r2 {continue;}
                    let tmp_score = calc_score2(&rooms[r1], &rooms[r2], ti);
                    if tmp_score > rooms[r2].score + rooms[r1].score && mx < tmp_score - rooms[r2].score - rooms[r1].score {
                        mx = tmp_score - rooms[r2].score - rooms[r1].score;
                        room_id = r2;
                    }
                }
                if room_id < INF {
                    let mut co = 0;
                    for &tti2 in rooms[room_id].ticks.iter() {
                        co += (ti - tti2)*2;
                    }
                    for &tti2 in rooms[r1].ticks.iter() {
                        co += (ti - tti2)*2;
                    }
                    let pi = rooms[r1].player_id[0];
                    ret.push((pi, rooms[room_id].player_id[0]));
                    rooms[room_id].player_id.push(pi);
                    let pi = rooms[r1].player_id[1];
                    rooms[room_id].player_id.push(pi);
                    rooms[room_id].s_max = rooms[room_id].s_max.max(rooms[r1].s_max);
                    rooms[room_id].s_min = rooms[room_id].s_min.min(rooms[r1].s_min);
                    rooms[room_id].score += mx + rooms[r1].score;
                    let tic = rooms[r1].ticks[0];
                    rooms[room_id].ticks.push(tic);
                    let tic = rooms[r1].ticks[1];
                    rooms[room_id].ticks.push(tic);
                    let sk = rooms[r1].player_sk[0];
                    rooms[room_id].player_sk.push(sk);
                    let sk = rooms[r1].player_sk[1];
                    rooms[room_id].player_sk.push(sk);
                    rooms[room_id].cost += co;
                    rooms[r1].used = true;
                }
            }
        }

        if (ti+1) % 36 == 0 {
            let r = rooms.len().min(40);
            let r2 = rooms.len().min(20);
            let rn = rooms.len();
            for r1 in rn-r..rn-r2 {
                if rooms[r1].used || rooms[r1].ticks.len() > 1 {continue;}
                let mut mx = 50;
                let mut room_id = INF;
                let si = rooms[r1].player_sk[0];
                let tti = rooms[r1].ticks[0];
                for r2 in rn-r..rn-r2 {
                    if rooms[r2].used || rooms[r2].ticks.len() == 4 || r1 == r2 {continue;}
                    let mut tmp_score = calc_score(&rooms[r2], ti, si);
                    tmp_score = tmp_score.saturating_sub((ti-tti)*rooms[r2].ticks.len());
                    //let sp = rooms[r2].s_max.max(si) - rooms[r2].s_min.min(si);
                    if tmp_score > rooms[r2].score && mx < tmp_score - rooms[r2].score{//} && sp < 6 {
                        mx = tmp_score - rooms[r2].score;
                        room_id = r2;
                    }
                    
                }
                if room_id < INF {
                    let mut co = 0;
                    for &tti2 in rooms[room_id].ticks.iter() {
                        co += ti - tti2;
                    }
                    co += (ti - tti)*rooms[room_id].ticks.len();
                    let pi = rooms[r1].player_id[0];
                    ret.push((pi, rooms[room_id].player_id[0]));
                    rooms[room_id].player_id.push(pi);
                    rooms[room_id].s_max = rooms[room_id].s_max.max(si);
                    rooms[room_id].s_min = rooms[room_id].s_min.min(si);
                    rooms[room_id].score += mx;
                    rooms[room_id].ticks.push(tti);
                    rooms[room_id].player_sk.push(si);
                    rooms[room_id].cost += co;
                    rooms[r1].used = true;
                }
            }
        }
        
        if ti+1 == T {
            let r = rooms.len().min(20);
            let rn = rooms.len();
            for r1 in rn-r..rn {
                if rooms[r1].used || rooms[r1].ticks.len() > 1 {continue;}
                let mut mx = 0;
                let mut room_id = INF;
                let si = rooms[r1].player_sk[0];
                let tti = rooms[r1].ticks[0];
                for r2 in rn-r..rn {
                    if rooms[r2].used || rooms[r2].ticks.len() == 4 || r1 == r2 {continue;}
                    let mut tmp_score = calc_score(&rooms[r2], ti, si);
                    tmp_score = tmp_score.saturating_sub((ti-tti)*rooms[r2].ticks.len());
                    //let sp = rooms[r2].s_max.max(si) - rooms[r2].s_min.min(si);
                    if tmp_score > rooms[r2].score && mx < tmp_score - rooms[r2].score {
                        mx = tmp_score - rooms[r2].score;
                        room_id = r2;
                    }
                    
                }
                if room_id < INF {
                    let mut co = 0;
                    for &tti2 in rooms[room_id].ticks.iter() {
                        co += ti - tti2;
                    }
                    co += (ti - tti)*rooms[room_id].ticks.len();
                    let pi = rooms[r1].player_id[0];
                    ret.push((pi, rooms[room_id].player_id[0]));
                    rooms[room_id].player_id.push(pi);
                    rooms[room_id].s_max = rooms[room_id].s_max.max(si);
                    rooms[room_id].s_min = rooms[room_id].s_min.min(si);
                    rooms[room_id].score += mx;
                    rooms[room_id].ticks.push(tti);
                    rooms[room_id].player_sk.push(si);
                    rooms[room_id].cost += co;
                    rooms[r1].used = true;
                }
            }
        }
        write!(&mut stdout, "{}\n", ret.len()).unwrap();
        for (ui, vi) in ret {
            write!(&mut stdout, "{} {}\n", ui, vi).unwrap();
        }
        stdout.flush().unwrap();

    }
    
    let mut tscore = 0;
    for room in rooms {
        if room.ticks.len() > 0 && !room.used{
            tscore += room.score;
        }
    }
    eprintln!("{}", tscore);
    
}

yukicoder

結果

テストケース

ソースコード