結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 tomerun
|
| 提出日時 | 2026-02-26 00:30:53 |
| 言語 | Rust (1.93.0 + proconio + num + itertools) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 14,591 bytes |
| 記録 | |
| コンパイル時間 | 28,577 ms |
| コンパイル使用メモリ | 633,500 KB |
| 実行使用メモリ | 7,848 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2026-02-26 00:31:31 |
| 合計ジャッジ時間 | 34,121 ms |
|
ジャッジサーバーID （参考情報） |
judge6 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | RE * 100 |
ソースコード
// #![allow(unused_imports)]
// #![allow(dead_code)]
// #![allow(non_snake_case)]
use std::env;
use std::io::{self, BufRead, BufReader, Read, Stdin};
use std::mem;
use std::str::FromStr;
use std::string::String;
use std::time;
const TIMELIMIT: u64 = 950;
const INF: usize = 1 << 28;
const N: usize = 32;
const R: usize = 1000;
const M: usize = 400;
const K: usize = 25;
#[derive(Debug)]
pub struct Scanner<R> {
reader: BufReader<R>,
}
fn scanner() -> Scanner<Stdin> {
Scanner::new(io::stdin())
}
impl<R: io::Read> Scanner<R> {
pub fn new(read: R) -> Scanner<R> {
Scanner { reader: BufReader::new(read) }
}
pub fn next_str(&mut self) -> Option<String> {
let mut buf = [0; 1];
let size = self.reader.read(&mut buf).unwrap();
if size == 0 {
None
} else {
self.skip_whitespace(&mut buf)?;
let mut v = vec![buf[0]];
loop {
let size = self.reader.read(&mut buf).unwrap();
if size == 0 || buf[0].is_ascii_whitespace() {
break;
}
v.push(buf[0]);
}
Some(String::from_utf8(v).unwrap())
}
}
pub fn next_line(&mut self) -> String {
let mut line = String::new();
self.reader.read_line(&mut line).unwrap();
if let Some(s) = line.strip_suffix("\n") { s.to_string() } else { line }
}
pub fn next_as<S: FromStr>(&mut self) -> Option<S> {
let s = self.next_str()?;
S::from_str(&s).ok()
}
pub fn str(&mut self) -> String {
self.next_str().unwrap()
}
pub fn i32(&mut self) -> i32 {
self.next_as::<i32>().unwrap()
}
pub fn u32(&mut self) -> u32 {
self.next_as::<u32>().unwrap()
}
pub fn u64(&mut self) -> u64 {
self.next_as::<u64>().unwrap()
}
pub fn usize(&mut self) -> usize {
self.next_as::<usize>().unwrap()
}
fn skip_whitespace(&mut self, mut buf: &mut [u8]) -> Option<u8> {
loop {
if !buf[0].is_ascii_whitespace() {
return Some(buf[0]);
}
let size = self.reader.read(&mut buf).unwrap();
if size == 0 {
return None;
}
}
}
}
struct XorShift32 {
state: u32,
}
impl XorShift32 {
fn from_seed(seed: u32) -> Self {
let initial_state = if seed == 0 { 1 } else { seed };
XorShift32 { state: initial_state }
}
fn next_u32(&mut self) -> u32 {
let mut x = self.state;
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
self.state = x;
x
}
fn next_f64(&mut self) -> f64 {
self.next_u32() as f64 / (u32::MAX as f64 + 1.0)
}
}
#[derive(Debug)]
struct Timer {
start_time: time::Instant,
limit: time::Instant,
}
impl Timer {
fn new(tl: u64) -> Timer {
let start_time = time::Instant::now();
Timer { start_time, limit: start_time + time::Duration::from_millis(tl) }
}
fn elapsed(&self) -> u64 {
self.start_time.elapsed().as_millis() as u64
}
fn tl(&self) -> u64 {
(self.limit - self.start_time).as_millis() as u64
}
}
fn time_to_str(t: usize) -> String {
let h = t / 12 + 6;
let m = (t % 12) * 5;
format!("{:02}:{:02}", h, m)
}
struct Input {
ws: [u64; N],
start_at: [[[usize; N]; N]; 21],
dist: [[usize; N]; N],
far: [[bool; N]; N],
}
impl Input {
fn new() -> Input {
let mut sc = scanner();
sc.next_line();
let mut pos = [Pos::new(0, 0); N];
let mut ws = [0; N];
for i in 0..N {
let y = sc.i32() as usize;
let x = sc.i32() as usize;
let w = sc.u64();
pos[i] = Pos::new(y, x);
ws[i] = w;
}
let mut dist = [[0; N]; N];
let mut far = [[false; N]; N];
for i in 0..N {
for j in 0..N {
let d2 = pos[i].dist2(&pos[j]);
if d2 >= (R / 4) * (R / 4) {
far[i][j] = true;
}
dist[i][j] = (((d2 as f64).sqrt() * 60.0 / 800.0 + 40.0) / 5.0).ceil() as usize;
}
dist[i][i] = INF;
}
sc.usize();
let mut flight = vec![vec![]; N];
for _ in 0..M {
let a = sc.usize() - 1;
let ss = sc.str();
let b = sc.usize() - 1;
let ts = sc.str();
let s = ((ss[0..2].parse::<usize>().unwrap() - 6) * 60 + ss[3..5].parse::<usize>().unwrap()) / 5;
let t = ((ts[0..2].parse::<usize>().unwrap() - 6) * 60 + ts[3..5].parse::<usize>().unwrap()) / 5;
flight[b].push((a, s, t));
assert!(t - s == dist[a][b]);
}
let mut start_at = [[[INF; N]; N]; 21];
for i in 0..N {
let mut time = [INF; N];
for st in 0..=20 {
time[i] = st * 6 + 60;
let mut heap = std::collections::BinaryHeap::new();
heap.push((time[i], i));
while let Some((now, u)) = heap.pop() {
if time[u] < now {
continue;
}
for &(v, s, t) in &flight[u] {
if t <= now && (time[v] == INF || s > time[v]) {
time[v] = s;
heap.push((s, v));
}
}
}
for j in 0..N {
start_at[st][j][i] = time[j];
// eprintln!(
// "{:?}->{:?} {} {}",
// j,
// i,
// time_to_str(st * 6 + 60),
// if time[j] == INF { "-".to_string() } else { time_to_str(time[j]) }
// );
}
}
}
Input { ws, start_at, dist, far }
}
}
#[derive(Debug, Clone, Copy)]
struct Pos {
y: usize,
x: usize,
}
impl Pos {
fn new(y: usize, x: usize) -> Pos {
Pos { y, x }
}
fn dist2(&self, other: &Pos) -> usize {
let dy = self.y as i32 - other.y as i32;
let dx = self.x as i32 - other.x as i32;
(dy * dy + dx * dx) as usize
}
}
#[derive(Debug, Clone, Copy)]
struct Flight {
a: usize,
b: usize,
s: usize,
t: usize,
}
impl Flight {
fn new(a: usize, b: usize, s: usize, t: usize) -> Flight {
Flight { a, b, s, t }
}
}
#[derive(Debug, Clone)]
struct Result {
flights: Vec<Vec<Flight>>,
score: f64,
}
impl Result {
fn new(flights: Vec<Vec<Flight>>, score: f64) -> Result {
Result { flights, score }
}
fn new_empty() -> Result {
Result { flights: vec![vec![]; K], score: 0.0 }
}
fn output(&self) {
for i in 0..K {
println!("{}", self.flights[i].len());
for f in &self.flights[i] {
println!("{} {} {} {}", f.a + 1, time_to_str(f.s), f.b + 1, time_to_str(f.t));
}
}
}
}
struct Solver {
input: Input,
timer: Timer,
rng: XorShift32,
start_at: [[[usize; N]; N]; 21],
}
impl Solver {
fn new(input: Input) -> Solver {
let tl = env::var("TL").map_or(TIMELIMIT, |v| v.parse().unwrap());
let timer = Timer::new(tl);
let rng = XorShift32::from_seed(2);
let start_at = [[[INF; N]; N]; 21];
Solver { input, timer, rng, start_at }
}
fn calc_score(&mut self, flights: &[Vec<Flight>]) -> (f64, [[[usize; N]; N]; 21]) {
let mut direct = vec![vec![]; N];
for fs in flights {
for f in fs {
direct[f.b].push((f.a, f.s, f.t));
}
}
for i in 0..self.start_at.len() {
for j in 0..N {
self.start_at[i][j].fill(INF);
}
}
let mut start_at = [[[INF; N]; N]; 21];
for i in 0..N {
let mut time = [INF; N];
for st in 0..=20 {
time[i] = st * 6 + 60;
let mut heap = std::collections::BinaryHeap::new();
heap.push((time[i], i));
while let Some((now, u)) = heap.pop() {
if time[u] < now {
continue;
}
for &(v, s, t) in &direct[u] {
if t <= now && (time[v] == INF || s > time[v]) {
time[v] = s;
heap.push((s, v));
}
}
}
for j in 0..N {
start_at[st][j][i] = time[j];
// eprintln!(
// "{:?}->{:?} {} {}",
// j,
// i,
// time_to_str(st * 6 + 60),
// if time[j] == INF { "-".to_string() } else { time_to_str(time[j]) }
// );
}
}
}
let mut v_sq = 0;
let mut v_ci = 0;
for i in 0..N {
for j in 0..N {
if !self.input.far[i][j] {
continue;
}
for k in 0..=20 {
let v0 = self.input.start_at[k][i][j];
let v1 = start_at[k][i][j];
if v1 != INF && (v0 == INF || v0 < v1) {
// eprintln!(
// "ci: {:?} {:?} {:?} {:?} {:?} {:?}",
// i,
// j,
// k,
// v0,
// v1,
// self.input.ws[i] * self.input.ws[j] / 10_000_000_000
// );
v_ci += self.input.ws[i] * self.input.ws[j];
} else {
v_sq += self.input.ws[i] * self.input.ws[j];
}
}
}
}
// eprintln!("v_sq:{:?} v_ci:{:?}", v_sq / 10_000_000_000, v_ci / 10_000_000_000);
(v_ci as f64 / (v_ci + v_sq) as f64, start_at)
}
fn random_flight(&mut self) -> Vec<Flight> {
let mut flights = vec![];
let max_v = self.rng.next_u32() as usize % (N / 2 - N / 10 + 1) + N / 10;
let mut now = self.rng.next_u32() as usize % 1;
let mut pos = self.rng.next_u32() as usize % max_v;
let mut fail = 0;
loop {
if now < 170 {
let mut found = false;
for i in 0..N / 10 {
let d = self.input.dist[pos][i];
if now + d > 180 {
continue;
}
let nt = if now + d < 60 { 0 } else { (now + d - 60) / 6 };
if self.start_at[nt][pos][i] == INF {
flights.push(Flight::new(pos, i, now, now + d));
now += d;
pos = i;
found = true;
}
}
if found {
continue;
}
}
let mv = if fail > 10 { N - 1 } else { max_v - 1 };
let mut next = self.rng.next_u32() as usize % mv;
if next >= pos {
next += 1;
}
let wait = self.rng.next_u32() as usize % 2;
let d = self.input.dist[pos][next];
if now + d + wait > 180 {
fail += 1;
if fail == 100 {
break;
}
continue;
}
flights.push(Flight::new(pos, next, now + wait, now + wait + d));
now += wait + d;
pos = next;
}
flights
}
fn solve(&mut self, tl: u64) -> Result {
let mut flights = vec![];
for _ in 0..K {
flights.push(self.random_flight());
}
let (mut cur_score, start_at) = self.calc_score(&flights);
self.start_at = start_at;
let mut best_score = cur_score;
let mut best_flights = flights.clone();
let initial_cooler: f64 = env::var("IC").map_or(100.0, |v| v.parse().unwrap());
let final_cooler: f64 = env::var("FC").map_or(1000.0, |v| v.parse().unwrap());
let mut cooler = initial_cooler;
let begin_time = self.timer.elapsed();
let mut turn = 0;
loop {
if turn & 0xF == 0 {
let elapsed = self.timer.elapsed();
if elapsed > tl {
eprintln!("total_turn: {}", turn);
break;
}
let ratio = (elapsed - begin_time) as f64 / (TIMELIMIT - begin_time) as f64;
cooler = (initial_cooler.ln() * (1.0 - ratio) + final_cooler.ln() * ratio).exp();
}
turn += 1;
let ch_fi = self.rng.next_u32() as usize % K;
let new_flights = self.random_flight();
let old_flights = mem::replace(&mut flights[ch_fi], new_flights);
let (new_score, new_start_at) = self.calc_score(&flights);
if self.accept(new_score - cur_score, cooler) {
cur_score = new_score;
self.start_at = new_start_at;
if cur_score > best_score {
eprintln!("best_score:{:?} at turn:{:?}", cur_score, turn);
best_score = cur_score;
best_flights = flights.clone();
}
} else {
flights[ch_fi] = old_flights;
}
}
Result::new(best_flights, best_score)
}
fn accept(&mut self, diff: f64, cooler: f64) -> bool {
if diff >= 0.0 {
return true;
}
let v = diff as f64 * cooler;
if v < -6.0 {
return false;
}
return self.rng.next_f64() < v.exp();
}
}
fn main() {
let input = Input::new();
let mut solver = Solver::new(input);
let mut best_res = Result::new_empty();
let part = env::var("PART").map_or(1, |v| v.parse().unwrap());
for i in 0..part {
let result = solver.solve(solver.timer.tl() * (i + 1) / part);
if result.score > best_res.score {
best_res = result;
}
}
best_res.output();
eprintln!("final_score:{:?}", (best_res.score * 1e6) as i64);
}