結果
| 問題 |
No.5020 Averaging
|
| ユーザー |
 komorin95
|
| 提出日時 | 2025-04-11 16:13:34 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 11,214 bytes |
| コンパイル時間 | 13,635 ms |
| コンパイル使用メモリ | 394,248 KB |
| 実行使用メモリ | 7,848 KB |
| スコア | 18,615,875 |
| 最終ジャッジ日時 | 2025-04-11 16:14:42 |
| 合計ジャッジ時間 | 60,893 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 46 TLE * 4 |
コンパイルメッセージ
warning: unused imports: `BufReader` and `stdin`
--> src/main.rs:345:15
|
345 | use std::io::{stdin, BufReader};
| ^^^^^ ^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: function `card_error_max` is never used
--> src/main.rs:163:4
|
163 | fn card_error_max(u: (u64, u64)) -> u64 {
| ^^^^^^^^^^^^^^
|
= note: `#[warn(dead_code)]` on by default
warning: function `card_error_sum` is never used
--> src/main.rs:167:4
|
167 | fn card_error_sum(u: (u64, u64)) -> u64 {
| ^^^^^^^^^^^^^^
warning: function `sign` is never used
--> src/main.rs:191:4
|
191 | fn sign(p1: (u64, u64), p2: (u64, u64), p3: (u64, u64)) -> i128 {
| ^^^^
warning: function `point_in_triangle_i128` is never used
--> src/main.rs:202:4
|
202 | fn point_in_triangle_i128(pt: (u64, u64), a: (u64, u64), b: (u64, u64), c: (u64, u64)) -> bool {
| ^^^^^^^^^^^^^^^^^^^^^^
ソースコード
// -*- coding:utf-8-unix -*-
use proconio::{fastout, input};
const TARGET: u64 = 500_000_000_000_000_000;
const MINV: u64 = 100_000_000_000_000_000;
const TARGET_ADJ: u64 = TARGET - MINV;
const OP_NUM: usize = 50;
#[fastout]
fn main() {
let _ = get_time();
input! {
n: usize,
mut ab: [(u64, u64); n],
}
// adjust value interval
for x in &mut ab {
x.0 -= MINV;
x.1 -= MINV;
}
let mut triangle_valuations = SegmentTree::new(
(n - 1) * (n - 2) / 2,
|| (u64::MAX, u64::MAX, u64::MAX),
|x, y| x.min(y),
);
for i in 1..n {
for j in i + 1..n {
triangle_valuations.update(triangle_num(i, j), triangle_val_l0(ab[0], ab[i], ab[j]));
}
}
let mut ans = Vec::new();
for _ in 0..OP_NUM {
// choose 0
let mut best_v = 0;
let mut best_score_v = (u64::MAX, u64::MAX, u64::MAX);
for v in 1..n {
let old_ab0 = ab[0];
let old_abv = ab[v];
let new_ab = card_avg(ab[0], ab[v]);
ab[0] = new_ab;
ab[v] = new_ab;
let mut score_new = (u64::MAX, u64::MAX, u64::MAX);
for i in 1..n {
for j in i + 1..n {
score_new = score_new.min(triangle_val_l0(ab[0], ab[i], ab[j]));
}
}
if score_new < best_score_v {
best_score_v = score_new;
best_v = v;
}
ab[0] = old_ab0;
ab[v] = old_abv;
}
// not choose 0
let mut best_uv = (0, 0);
let mut best_score_uv = (u64::MAX, u64::MAX, u64::MAX);
let mut old_tr_score_u = vec![(u64::MAX, u64::MAX, u64::MAX); n];
let mut old_tr_score_v = vec![(u64::MAX, u64::MAX, u64::MAX); n];
for u in 1..n {
for v in u + 1..n {
// modify ab
let old_abu = ab[u];
let old_abv = ab[v];
let new_ab = card_avg(ab[u], ab[v]);
ab[u] = new_ab;
ab[v] = new_ab;
// recalc for u
for k in 1..n {
if k == u {
continue;
}
let i = k.min(u);
let j = k.max(u);
let trnum = triangle_num(i, j);
old_tr_score_u[k] = triangle_valuations.query_onepoint(trnum);
triangle_valuations.update(trnum, triangle_val_l0(ab[0], ab[i], ab[j]));
}
// recalc for v
for k in 1..n {
if k == v {
continue;
}
let i = k.min(v);
let j = k.max(v);
let trnum = triangle_num(i, j);
old_tr_score_v[k] = triangle_valuations.query_onepoint(trnum);
triangle_valuations.update(trnum, triangle_val_l0(ab[0], ab[i], ab[j]));
}
let thisscore = triangle_valuations.query(0..(n - 1) * (n - 2) / 2);
if best_score_uv > thisscore {
best_score_uv = thisscore;
best_uv = (u, v);
}
// restore valuations
for k in 1..n {
if k == u {
continue;
}
let i = k.min(u);
let j = k.max(u);
let trnum = triangle_num(i, j);
triangle_valuations.update(trnum, old_tr_score_u[k]);
}
for k in 1..n {
if k == v {
continue;
}
let i = k.min(v);
let j = k.max(v);
let trnum = triangle_num(i, j);
triangle_valuations.update(trnum, old_tr_score_v[k]);
}
// restore ab
ab[u] = old_abu;
ab[v] = old_abv;
}
}
// update
if best_score_v <= best_score_uv {
if best_v == 0 {
break;
}
ans.push((0, best_v));
ab[0] = card_avg(ab[0], ab[best_v]);
} else {
if best_uv == (0, 0) {
break;
}
ans.push(best_uv);
let (u, v) = best_uv;
let newab = card_avg(ab[u], ab[v]);
ab[u] = newab;
ab[v] = newab;
}
for i in 1..n {
for j in i + 1..n {
triangle_valuations
.update(triangle_num(i, j), triangle_val_l0(ab[0], ab[i], ab[j]));
}
}
}
println!("{}", ans.len());
for &(u, v) in &ans {
println!("{} {}", u + 1, v + 1);
}
}
fn card_avg(u: (u64, u64), v: (u64, u64)) -> (u64, u64) {
((u.0 + v.0) / 2, (u.1 + v.1) / 2)
}
fn card_error_max(u: (u64, u64)) -> u64 {
(u.0.abs_diff(TARGET_ADJ)).max(u.1.abs_diff(TARGET_ADJ))
}
fn card_error_sum(u: (u64, u64)) -> u64 {
(u.0.abs_diff(TARGET_ADJ)) + (u.1.abs_diff(TARGET_ADJ))
}
fn triangle_num(u: usize, v: usize) -> usize {
(v - 1) * (v - 2) / 2 + u - 1
}
fn triangle_val_l0(a: (u64, u64), b: (u64, u64), c: (u64, u64)) -> (u64, u64, u64) {
if !point_in_triangle((TARGET_ADJ, TARGET_ADJ), a, b, c) {
return (u64::MAX, u64::MAX, u64::MAX);
}
let mut vals = [l0_len(a, b), l0_len(b, c), l0_len(c, a)];
vals.sort_unstable();
return (vals[2], vals[1], vals[0]);
}
fn l0_len(a: (u64, u64), b: (u64, u64)) -> u64 {
a.0.abs_diff(b.0).max(a.1.abs_diff(b.1))
}
/// 3点 p1, p2, p3 の順序で作る平面上の「向き」を、クロス積の符号で返す関数
/// 計算式は (p1 - p3) × (p2 - p3) となり、
/// 正なら p3 を起点として p1->p2 が反時計回り、負なら時計回り、0 なら 3 点は同一直線上にあることを意味する。
fn sign(p1: (u64, u64), p2: (u64, u64), p3: (u64, u64)) -> i128 {
(p1.0 as i128 - p3.0 as i128) * (p2.1 as i128 - p3.1 as i128)
- (p2.0 as i128 - p3.0 as i128) * (p1.1 as i128 - p3.1 as i128)
}
fn sign_f64(p1: (u64, u64), p2: (u64, u64), p3: (u64, u64)) -> f64 {
(p1.0 as f64 - p3.0 as f64) * (p2.1 as f64 - p3.1 as f64)
- (p2.0 as f64 - p3.0 as f64) * (p1.1 as f64 - p3.1 as f64)
}
/// 点 `pt` が、頂点 a, b, c で作られる三角形の内部（もしくは境界上）にあるかを判定する関数
fn point_in_triangle_i128(pt: (u64, u64), a: (u64, u64), b: (u64, u64), c: (u64, u64)) -> bool {
// 各エッジに対して、pt の位置関係をクロス積の符号で評価する
let d1 = sign(pt, a, b);
let d2 = sign(pt, b, c);
let d3 = sign(pt, c, a);
// d1, d2, d3 のうち、負の値を持つかどうか
let has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
// 同様に正の値が存在するか
let has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);
// すべての符号が同じ（または 0 を含む）なら pt は三角形内
!(has_neg && has_pos)
}
fn point_in_triangle(pt: (u64, u64), a: (u64, u64), b: (u64, u64), c: (u64, u64)) -> bool {
// 各エッジに対して、pt の位置関係をクロス積の符号で評価する
let d1 = sign_f64(pt, a, b);
let d2 = sign_f64(pt, b, c);
let d3 = sign_f64(pt, c, a);
// d1, d2, d3 のうち、負の値を持つかどうか
let has_neg = (d1 < 0.) || (d2 < 0.) || (d3 < 0.);
// 同様に正の値が存在するか
let has_pos = (d1 > 0.) || (d2 > 0.) || (d3 > 0.);
// すべての符号が同じ（または 0 を含む）なら pt は三角形内
!(has_neg && has_pos)
}
//
// MARK: Time Measurement
//
pub fn get_time() -> f64 {
static mut STIME: f64 = -1.0;
let t = std::time::SystemTime::now()
.duration_since(std::time::UNIX_EPOCH)
.unwrap();
let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
unsafe {
if STIME < 0.0 {
STIME = ms;
}
ms - STIME
}
}
#[allow(unused)]
#[cfg(debug_assertions)]
const TIME_LIMIT: f64 = 10.;
#[allow(unused)]
#[cfg(not(debug_assertions))]
const TIME_LIMIT: f64 = 2.9;
// Segment tree for range minimum query and alike problems
// The closures must fulfill the defining laws of monoids
// Indexing is 0-based
// The code is based on that in C++ in the 'ant book'
#[derive(Clone, PartialEq, Debug)]
struct SegmentTree<A, CUnit, CMult> {
data: Vec<A>,
monoid_unit_closure: CUnit,
monoid_op_closure: CMult,
}
#[allow(dead_code)]
impl<A, CUnit, CMult> SegmentTree<A, CUnit, CMult>
where
A: Copy,
CUnit: Fn() -> A,
CMult: Fn(A, A) -> A,
{
fn new(n: usize, monoid_unit_closure: CUnit, monoid_op_closure: CMult) -> Self {
let mut nn = 1;
while nn < n {
nn *= 2;
}
let this = Self {
data: vec![monoid_unit_closure(); 2 * nn - 1],
monoid_unit_closure,
monoid_op_closure,
};
return this;
}
fn query_onepoint(&self, k: usize) -> A {
let nn = (self.data.len() + 1) / 2;
return self.data[k + nn - 1];
}
fn from_slice(sl: &[A], monoid_unit_closure: CUnit, monoid_op_closure: CMult) -> Self {
let n = sl.len();
let mut nn = 1;
while nn < n {
nn *= 2;
}
let mut data = vec![monoid_unit_closure(); 2 * nn - 1];
for k in 0..n {
data[k + nn - 1] = sl[k];
}
if n >= 2 {
for j in (0..=(n + nn - 3) / 2).rev() {
data[j] = (monoid_op_closure)(data[j * 2 + 1], data[j * 2 + 2]);
}
}
Self {
data,
monoid_unit_closure,
monoid_op_closure,
}
}
fn update(&mut self, k: usize, a: A) {
let n = (self.data.len() + 1) / 2;
let mut k = k + n - 1;
self.data[k] = a;
while k > 0 {
k = (k - 1) / 2;
self.data[k] = (self.monoid_op_closure)(self.data[k * 2 + 1], self.data[k * 2 + 2]);
}
}
fn query_internal(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> A {
if r <= a || b <= l {
return (self.monoid_unit_closure)();
}
if a <= l && r <= b {
return self.data[k];
} else {
let vl = self.query_internal(a, b, k * 2 + 1, l, (l + r) / 2);
let vr = self.query_internal(a, b, k * 2 + 2, (l + r) / 2, r);
return (self.monoid_op_closure)(vl, vr);
}
}
}
trait RangeQuery<T> {
type Output;
fn query(&self, r: T) -> Self::Output;
}
use std::io::{stdin, BufReader};
use std::ops::Range;
#[allow(dead_code)]
impl<A, CUnit, CMult> RangeQuery<Range<usize>> for SegmentTree<A, CUnit, CMult>
where
A: Copy,
CUnit: Fn() -> A,
CMult: Fn(A, A) -> A,
{
type Output = A;
fn query(&self, range: Range<usize>) -> A {
let n = (self.data.len() + 1) / 2;
return self.query_internal(range.start, range.end, 0, 0, n);
}
}