#![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::>(); 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::>() }; ($it:ident; [u8]) => { Vec::from(_read!($it; String).into_bytes()) }; ($it:ident; usize1) => { $it.next().unwrap_or_else(|| panic!("input mismatch")).parse::().unwrap_or_else(|e| panic!("{}", e)) - 1 }; ($it:ident; [usize1]) => { $it.map(|s| s.parse::().unwrap_or_else(|e| panic!("{}", e)) - 1).collect::>() }; ($it:ident; [$t:ty]) => { $it.map(|s| s.parse::<$t>().unwrap_or_else(|e| panic!("{}", e))).collect::>() }; ($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, cost: usize, score: usize, player_sk: Vec, player_id: Vec, 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 = 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::().unwrap(); let mut ret: Vec<(usize, usize)> = vec![]; for ii in 0..n { num_player += 1; let si = sv[ii+1].parse::().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 = 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); }