結果
| 問題 | No.5004 Room Assignment |
| ユーザー |
 ts_
|
| 提出日時 | 2021-12-02 07:25:20 |
| 言語 | Rust (1.77.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 11,954 bytes |
| コンパイル時間 | 2,312 ms |
| 実行使用メモリ | 39,860 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2021-12-02 07:25:36 |
| 合計ジャッジ時間 | 14,892 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / 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 | -- | - |
ソースコード
#![allow(unused_imports)]
#![allow(dead_code)]
#![allow(unused_macros)]
use std::{collections::{VecDeque, HashSet}, io::{StdoutLock, prelude::*}, writeln};
use std::io::{BufWriter};
/*
use std::io::Read;
macro_rules! input {
($iter:expr) => {};
($iter:expr, ) => {};
($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read!($iter, $t);
input!{$iter $($r)*}
};
($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => {
let mut $var = read!($iter, $t);
input!{$iter $($r)*}
};
}
macro_rules! read {
($iter:expr, ( $($t:tt),* )) => {
( $(read!($iter, $t)),* )
};
($iter:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read!($iter, $t)).collect::<Vec<_>>()
};
($iter:expr, chars) => {
read!($iter, String).chars().collect::<Vec<char>>()
};
($iter:expr, usize1) => {
read!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
*/
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 (_, _) = read!(input, (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 n = read!(input, usize);
let mut ret: Vec<(usize, usize)> = vec![];
for _pi in 0..n {
num_player += 1;
let si = read!(usize);
//let si = read!(input, usize);
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 = 100;
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);
}