結果
| 問題 | No.5020 Averaging |
| コンテスト | |
| ユーザー |
 Tekyla
|
| 提出日時 | 2026-06-03 22:32:55 |
| 言語 | Rust (1.94.0 + proconio + num + itertools) |
| 結果 |
AC
|
| 実行時間 | 16 ms / 1,000 ms |
| コード長 | 25,411 bytes |
| 記録 | |
| コンパイル時間 | 13,169 ms |
| コンパイル使用メモリ | 211,356 KB |
| 実行使用メモリ | 6,400 KB |
| スコア | 33,539,616 |
| 最終ジャッジ日時 | 2026-06-03 22:33:12 |
| 合計ジャッジ時間 | 15,935 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_1 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
コンパイルメッセージ
warning: unexpected `cfg` condition value: `local`
--> src/main.rs:724:15
|
724 | #[cfg(feature = "local")]
| ^^^^^^^^^^^^^^^^^ help: remove the condition
|
= note: no expected values for `feature`
= help: consider adding `local` as a feature in `Cargo.toml`
= note: see <https://doc.rust-lang.org/nightly/rustc/check-cfg/cargo-specifics.html> for more information about checking conditional configuration
= note: `#[warn(unexpected_cfgs)]` on by default
warning: unexpected `cfg` condition value: `local`
--> src/main.rs:728:19
|
728 | #[cfg(not(feature = "local"))]
| ^^^^^^^^^^^^^^^^^ help: remove the condition
|
= note: no expected values for `feature`
= help: consider adding `local` as a feature in `Cargo.toml`
= note: see <https://doc.rust-lang.org/nightly/rustc/check-cfg/cargo-specifics.html> for more information about checking conditional configuration
warning: value assigned to `dist` is never read
--> src/main.rs:216:36
|
216 | let mut dist = 0;
| ^
|
= help: maybe it is overwritten before being read?
= note: `#[warn(unused_assignments)]` (part of `#[warn(unused)]`) on by default
warning: variable does not need to be mutable
--> src/main.rs:254:13
|
254 | let mut i = 0;
| ----^
| |
| help: remove this `mut`
|
= note: `#[warn(unused_mut)]` (part of `#[warn(unused)]`) on by default
warning: value assigned to `dist` is never read
--> src/main.rs:309:36
|
309 | let mut dist = 0;
| ^
|
= help: maybe it is overwritten before being read?
warning: variable does not need to be mutable
--> src/main.rs:335:22
|
335 | fn solver5(n: usize, mut ab: Vec<(i64, i64)>) -> Vec<(usize, usize)> {
| ----^^
|
ソースコード
// https://yukicoder.me/problems/no/5020
use proconio::input;
use std::collections::HashSet;
//const LOCAL_EXECUTE:bool = true;
const TARGET: i64 = 500_000_000_000_000_000;
const OPERATION_LIMIT: usize = 50;
fn operatioin(u: usize, v: usize, ab: &mut [(i64, i64)]) {
let (a1, b1) = ab[u];
let (a2, b2) = ab[v];
let am = (a1 + a2) / 2;
let bm = (b1 + b2) / 2;
ab[u] = (am, bm);
ab[v] = (am, bm);
}
fn calc_score(mut ab: Vec<(i64, i64)>, op: &[(usize, usize)]) -> i64 {
for &(u, v) in op {
operatioin(u, v, &mut ab);
}
let (a, b) = ab[0];
let v1 = a.abs_diff(TARGET);
let v2 = b.abs_diff(TARGET);
let m = v1.max(v2);
let x = op.len() as i64;
if m == 0 {
return 2000050 - x;
}
let score = 2000000.0 - 100000.0 * f64::log10(m as f64 + 1.0);
score as i64
}
fn solver1(n: usize, mut ab: Vec<(i64, i64)>) -> Vec<(usize, usize)> {
// いったん全部の平均に近づくようにやってみる
// a_max - a_min と b_max - b_min の一番大きな組み合わせのカードで平均を取る
let mut ans = vec![];
for _ in 0..OPERATION_LIMIT {
// let mut dist_max = -1;
// let mut i = 0;
// let mut j = 0;
// for ii in 0..(n - 1) {
// let (ai, bi) = ab[ii];
// for jj in (ii + 1)..n {
// let (aj, bj) = ab[jj];
// let dist = (ai - aj).abs().max((bi - bj).abs());
// if dist > dist_max {
// dist_max = dist;
// i = ii;
// j = jj
// }
// }
// }
let (i, j) = (0..n - 1)
.into_iter()
.map(|i| {
let (dist, j) = (i + 1..n)
.into_iter()
.map(|j| {
let (ai, bi) = ab[i];
let (aj, bj) = ab[j];
let dist = ai.abs_diff(aj).max(bi.abs_diff(bj));
(dist, j)
})
.max()
.unwrap();
(dist, (i, j))
})
.max()
.unwrap()
.1;
ans.push((i, j));
operatioin(i, j, &mut ab);
}
ans
}
fn find_best(ab: &[(i64, i64)], ignore_idx: &mut HashSet<usize>) {
let (mut a_sum, mut b_sum) = (0, 0);
for &(a, b) in ab {
a_sum -= TARGET;
a_sum += a;
b_sum -= TARGET;
b_sum += b;
}
let mut best_dist = i64::MAX;
let mut best_idx = 1;
for (i, &(a, b)) in ab.iter().enumerate() {
if i == 0 {
continue;
}
if ignore_idx.contains(&i) {
continue;
}
let dist = (a_sum - a + TARGET).abs() + (b_sum - b + TARGET).abs();
if dist < best_dist {
best_dist = dist;
best_idx = i;
}
}
ignore_idx.insert(best_idx);
}
fn solver2(n: usize, mut ab: Vec<(i64, i64)>) -> Vec<(usize, usize)> {
// 仲間外れを1枚決めて、それ以外で solver1 の要領で中心に寄る
// 2段階に分けて2回それを行う
let mut ans = vec![];
let mut ignore_idx = HashSet::new();
for loops in 0..50 {
if loops % 10 == 0 {
find_best(&ab, &mut ignore_idx);
}
let mut dist_max = -1;
let mut i = 0;
let mut j = 0;
for ii in 0..(n - 1) {
if ignore_idx.contains(&ii) {
continue;
}
let (ai, bi) = ab[ii];
for jj in (ii + 1)..n {
if ignore_idx.contains(&jj) {
continue;
}
let (aj, bj) = ab[jj];
let dist = (ai - aj).abs().max((bi - bj).abs());
if dist > dist_max {
dist_max = dist;
i = ii;
j = jj
}
}
}
ans.push((i, j));
operatioin(i, j, &mut ab);
}
ans
}
fn solver3(n: usize, mut ab: Vec<(i64, i64)>) -> Vec<(usize, usize)> {
// 仲間外れを1枚決めて、それ以外で solver1 の要領で中心に寄る
// 2段階に分けて2回それを行う
// solver2ベースで48回おこない、最後の2回は全探索
let mut ans = vec![];
let mut ignore_idx = HashSet::new();
for loops in 0..48 {
if loops % 5 == 0 {
find_best(&ab, &mut ignore_idx);
}
let mut dist_max = -1;
let mut i = 0;
let mut j = 0;
for ii in 0..(n - 1) {
if ignore_idx.contains(&ii) {
continue;
}
let (ai, bi) = ab[ii];
for jj in (ii + 1)..n {
if ignore_idx.contains(&jj) {
continue;
}
let (aj, bj) = ab[jj];
let dist = (ai - aj).abs().max((bi - bj).abs());
if dist > dist_max {
dist_max = dist;
i = ii;
j = jj
}
}
}
ans.push((i, j));
operatioin(i, j, &mut ab);
}
// ここから最後の2回を全探索. 脳筋実装.
// こういうのをAIでいい感じにするべき
let (mut best_i0, mut best_i1, mut best_i2, mut best_i3) = (1, 2, 3, 4);
let mut best_dist = {
let &(a, b) = &ab[0];
((a - TARGET).abs()).max((b - TARGET).abs())
};
for i0 in 0..(n - 1) {
for i1 in (i0 + 1)..n {
let a0 = (&ab[i0].0 + &ab[i1].0) / 2;
let b0 = (&ab[i0].1 + &ab[i1].1) / 2;
let i2 = 0;
for i3 in 1..n {
if i0 == i2 {
if i1 == i3 {
let dist = ((a0 - TARGET).abs()).max((b0 - TARGET).abs());
if dist < best_dist {
best_dist = dist;
best_i0 = i0;
best_i1 = i1;
best_i2 = i2;
best_i3 = i3;
}
} else {
let dist = ((a0 + &ab[i3].0) / 2 - TARGET)
.abs()
.max(((b0 + &ab[i3].1) / 2 - TARGET).abs());
if dist < best_dist {
best_dist = dist;
best_i0 = i0;
best_i1 = i1;
best_i2 = i2;
best_i3 = i3;
}
}
} else {
let mut dist = 0;
if i0 == i3 || i1 == i3 {
dist = ((a0 + &ab[i2].0) / 2 - TARGET)
.abs()
.max(((b0 + &ab[i2].1) / 2 - TARGET).abs());
} else {
dist = ((&ab[i2].0 + &ab[i3].0) / 2 - TARGET)
.abs()
.max(((&ab[i2].1 + &ab[i3].1) / 2 - TARGET).abs());
}
if dist < best_dist {
best_dist = dist;
best_i0 = i0;
best_i1 = i1;
best_i2 = i2;
best_i3 = i3;
}
}
}
}
}
ans.push((best_i0, best_i1));
ans.push((best_i2, best_i3));
ans
}
fn solver4(n: usize, mut ab: Vec<(i64, i64)>) -> Vec<(usize, usize)> {
// 仲間外れを決めるのはおなじ
// ペアは必ず0とのペアとする
let mut ans = vec![];
let mut ignore_idx = HashSet::new();
for loops in 0..48 {
if loops % 3 == 0 {
find_best(&ab, &mut ignore_idx);
}
let mut dist_max = -1;
let mut i = 0;
let mut j = 0;
let (ai, bi) = ab[0];
for jj in 1..n {
if ignore_idx.contains(&jj) {
continue;
}
let (aj, bj) = ab[jj];
let dist = (ai - aj).abs().max((bi - bj).abs());
if dist > dist_max {
dist_max = dist;
j = jj
}
}
ans.push((i, j));
operatioin(i, j, &mut ab);
}
// ここから最後の2回を全探索. 脳筋実装.
// こういうのをAIでいい感じにするべき
let (mut best_i0, mut best_i1, mut best_i2, mut best_i3) = (1, 2, 3, 4);
let mut best_dist = {
let &(a, b) = &ab[0];
((a - TARGET).abs()).max((b - TARGET).abs())
};
for i0 in 0..(n - 1) {
for i1 in (i0 + 1)..n {
let a0 = (&ab[i0].0 + &ab[i1].0) / 2;
let b0 = (&ab[i0].1 + &ab[i1].1) / 2;
let i2 = 0;
for i3 in 1..n {
if i0 == i2 {
if i1 == i3 {
let dist = ((a0 - TARGET).abs()).max((b0 - TARGET).abs());
if dist < best_dist {
best_dist = dist;
best_i0 = i0;
best_i1 = i1;
best_i2 = i2;
best_i3 = i3;
}
} else {
let dist = ((a0 + &ab[i3].0) / 2 - TARGET)
.abs()
.max(((b0 + &ab[i3].1) / 2 - TARGET).abs());
if dist < best_dist {
best_dist = dist;
best_i0 = i0;
best_i1 = i1;
best_i2 = i2;
best_i3 = i3;
}
}
} else {
let mut dist = 0;
if i0 == i3 || i1 == i3 {
dist = ((a0 + &ab[i2].0) / 2 - TARGET)
.abs()
.max(((b0 + &ab[i2].1) / 2 - TARGET).abs());
} else {
dist = ((&ab[i2].0 + &ab[i3].0) / 2 - TARGET)
.abs()
.max(((&ab[i2].1 + &ab[i3].1) / 2 - TARGET).abs());
}
if dist < best_dist {
best_dist = dist;
best_i0 = i0;
best_i1 = i1;
best_i2 = i2;
best_i3 = i3;
}
}
}
}
}
ans.push((best_i0, best_i1));
ans.push((best_i2, best_i3));
ans
}
fn solver5(n: usize, mut ab: Vec<(i64, i64)>) -> Vec<(usize, usize)> {
// 時間いっぱい回してみる
// 最初の48回は本当にランダムに, 最後の2回は全探索
let mut timer = TimeKeeper::new(0.95);
let mut rng = XorShift32::new(0);
let mut ans = vec![];
let mut ans_dist = i64::MAX;
while !timer.isTimeOver() {
let mut ab_new = ab.clone();
let mut ans_tmp = vec![];
for _ in 0..48 {
let i = rng.next_range_usize(0, n - 1);
let mut j = rng.next_range_usize(0, n - 1);
if i == j {
j = (j + 1) % n;
}
ans_tmp.push((i, j));
operatioin(i, j, &mut ab_new);
}
// 二回の全探索, solver4から引用
let (mut best_i0, mut best_i1, mut best_i2, mut best_i3) = (1, 2, 3, 4);
let mut best_dist = {
let &(a, b) = &ab_new[0];
((a - TARGET).abs()).max((b - TARGET).abs())
};
for i0 in 0..(n - 1) {
for i1 in (i0 + 1)..n {
let a0 = (&ab_new[i0].0 + &ab_new[i1].0) / 2;
let b0 = (&ab_new[i0].1 + &ab_new[i1].1) / 2;
let i2 = 0;
for i3 in 1..n {
if i0 == i2 {
if i1 == i3 {
let dist = ((a0 - TARGET).abs()).max((b0 - TARGET).abs());
if dist < best_dist {
best_dist = dist;
best_i0 = i0;
best_i1 = i1;
best_i2 = i2;
best_i3 = i3;
}
} else {
let dist = ((a0 + &ab_new[i3].0) / 2 - TARGET)
.abs()
.max(((b0 + &ab_new[i3].1) / 2 - TARGET).abs());
if dist < best_dist {
best_dist = dist;
best_i0 = i0;
best_i1 = i1;
best_i2 = i2;
best_i3 = i3;
}
}
} else {
let mut dist = 0;
if i0 == i3 || i1 == i3 {
dist = ((a0 + &ab_new[i2].0) / 2 - TARGET)
.abs()
.max(((b0 + &ab_new[i2].1) / 2 - TARGET).abs());
} else {
dist = ((&ab_new[i2].0 + &ab_new[i3].0) / 2 - TARGET)
.abs()
.max(((&ab_new[i2].1 + &ab_new[i3].1) / 2 - TARGET).abs());
}
if dist < best_dist {
best_dist = dist;
best_i0 = i0;
best_i1 = i1;
best_i2 = i2;
best_i3 = i3;
}
}
}
}
}
if best_dist < ans_dist {
ans_dist = best_dist;
ans_tmp.push((best_i0, best_i1));
ans_tmp.push((best_i2, best_i3));
ans = ans_tmp;
}
}
ans
}
fn solver6_mini(
n: usize,
ab: &Vec<(i64, i64)>,
target: usize,
target_a: i64,
target_b: i64,
ignore_idx: &HashSet<usize>,
) -> Vec<(usize, usize)> {
// ignore_idxを使わず、targetを(target_a, target_b)に近づける
let mut best_ans: Vec<(usize, usize)> = vec![];
let mut best_dist = (ab[target].0 - target_a).abs() + (ab[target].1 - target_b).abs();
// 1回の操作
let &(a0, b0) = &ab[target];
for j in 0..n {
if ignore_idx.contains(&j) || j == target {
continue;
}
let &(a1, b1) = &ab[j];
let dist = ((a0 + a1) / 2 - target_a).abs() + ((b0 + b1) / 2 - target_b).abs();
if dist < best_dist {
best_dist = dist;
best_ans = vec![(target, j)];
}
}
// 2回の操作
for j in 0..(n - 1) {
if ignore_idx.contains(&j) {
continue;
}
let &(a1, b1) = &ab[j];
for k in (j + 1)..n {
if ignore_idx.contains(&k) {
continue;
}
let &(a2, b2) = &ab[k];
let (a3, b3) = ((a1 + a2) / 2, (b1 + b2) / 2);
if j == target || k == target {
for l in 0..n {
if ignore_idx.contains(&l) || l == target {
continue;
}
let &(a4, b4) = &ab[l];
let (a5, b5) = ((a3 + a4) / 2, (b3 + b4) / 2);
let dist = (a5 - target_a).abs() + (b5 - target_b).abs();
if dist < best_dist {
best_dist = dist;
best_ans = vec![(j, k), (target, l)];
}
}
} else {
let (a4, b4) = ((a3 + a0) / 2, (b3 + b0) / 2);
let dist = (a4 - target_a).abs() + (b4 - target_b).abs();
if dist < best_dist {
best_dist = dist;
best_ans = vec![(j, k), (target, j)];
}
}
}
}
best_ans
}
fn solver6_mini2(
n: usize,
ab: &Vec<(i64, i64)>,
target_a: i64,
target_b: i64,
ignore_idx: &HashSet<usize>,
) -> (Vec<(usize, usize)>, usize) {
// ignore_idxを使わず、なにかを(target_a, target_b)に近づける
let mut best_ans: Vec<(usize, usize)> = vec![];
let mut best_dist = i64::MAX;
let mut best_idx = 0usize;
for i in 0..n {
if ignore_idx.contains(&i) {
continue;
}
let dist = (&ab[i].0 - target_a).abs() + (&ab[i].1 - target_b).abs();
if dist < best_dist {
best_dist = dist;
best_idx = i;
}
}
// 1回の操作
for i in 0..(n - 1) {
if ignore_idx.contains(&i) {
continue;
}
let &(a0, b0) = &ab[i];
for j in (i + 1)..n {
if ignore_idx.contains(&j) {
continue;
}
let &(a1, b1) = &ab[j];
let dist = ((a0 + a1) / 2 - target_a).abs() + ((b0 + b1) / 2 - target_b).abs();
if dist < best_dist {
best_dist = dist;
best_ans = vec![(i, j)];
best_idx = i;
}
}
}
// 2回の操作
for j in 0..(n - 1) {
if ignore_idx.contains(&j) {
continue;
}
let &(a1, b1) = &ab[j];
for k in (j + 1)..n {
if ignore_idx.contains(&k) {
continue;
}
let &(a2, b2) = &ab[k];
let (a3, b3) = ((a1 + a2) / 2, (b1 + b2) / 2);
// ここから作業
for l in 0..n {
if ignore_idx.contains(&l) || l == j {
continue;
}
let &(a4, b4) = &ab[l];
let (a5, b5) = ((a3 + a4) / 2, (b3 + b4) / 2);
let dist = (a5 - target_a).abs() + (b5 - target_b).abs();
if dist < best_dist {
best_dist = dist;
best_ans = vec![(j, k), (j, l)];
best_idx = j;
}
}
}
}
(best_ans, best_idx)
}
fn solver6(n: usize, mut ab: Vec<(i64, i64)>) -> Vec<(usize, usize)> {
// 0をまず2回使って重心の反対側に持っていく(sum(xi)/(N-2), sum(yi)/(N-2))
// 45回、0以外でランダム操作
// 2回使って0の反対側に何かしら設置
// 最後の1回で0を中心に持っていく
// 以上を時間いっぱい繰り返す
let mut timer = TimeKeeper::new(0.95);
let mut rng = XorShift32::new(0);
// abを先にTARGET分だけ引いておき、その後0を反対側に持っていく
let mut ignore_idx = HashSet::new();
let (mut sum_a, mut sum_b) = (0, 0);
ab[0].0 -= TARGET;
ab[0].1 -= TARGET;
for i in 1..n {
ab[i].0 -= TARGET;
ab[i].1 -= TARGET;
sum_a += ab[i].0;
sum_b += ab[i].1;
}
let mut ans = solver6_mini(
n,
&ab,
0,
-sum_a / (n as i64 - 2),
-sum_b / (n as i64 - 2),
&ignore_idx,
);
for &(i, j) in &ans {
operatioin(i, j, &mut ab);
}
let mut ans_dist = i64::MAX;
let mut best_ans: Vec<(usize, usize)> = vec![];
ignore_idx.insert(0);
while !timer.isTimeOver() {
let mut ab_new = ab.clone();
let mut ans_tmp = vec![];
for _ in ans.len()..47 {
let i = rng.next_range_usize(1, n - 1);
let mut j = rng.next_range_usize(1, n - 1);
if i == j {
j += 1;
if j >= n {
j = 1;
}
}
ans_tmp.push((i, j));
operatioin(i, j, &mut ab_new);
}
// 最後に反対側にいい感じのを作って0と合わせる
let (op, i) = solver6_mini2(n, &ab_new, -&ab_new[0].0, -&ab_new[0].1, &ignore_idx);
for (j, k) in op {
ans_tmp.push((j, k));
operatioin(j, k, &mut ab_new);
}
ans_tmp.push((0, i));
operatioin(0, i, &mut ab_new);
let dist = &ab_new[0].0.abs() + &ab_new[0].1.abs();
if dist < ans_dist {
ans_dist = dist;
best_ans = ans_tmp;
}
}
ans.append(&mut best_ans);
ans
}
fn solver7(n: usize, mut ab: Vec<(i64, i64)>) -> Vec<(usize, usize)> {
// 0をまず2回使って重心の反対側に持っていく(sum(xi)/(N-2), sum(yi)/(N-2))
// 最大45回、0の反対側に何かしら近づける
// 2回使って0の反対側に何かしら設置
// 最後の1回で0を中心に持っていく
// 以上を時間いっぱい繰り返す
let mut timer = TimeKeeper::new(0.95);
let mut rng = XorShift32::new(0);
// abを先にTARGET分だけ引いておき、その後0を反対側に持っていく
let mut ignore_idx = HashSet::new();
let (mut sum_a, mut sum_b) = (0, 0);
ab[0].0 -= TARGET;
ab[0].1 -= TARGET;
for i in 1..n {
ab[i].0 -= TARGET;
ab[i].1 -= TARGET;
sum_a += ab[i].0;
sum_b += ab[i].1;
}
let mut ans = solver6_mini(
n,
&ab,
0,
-sum_a / (n as i64 - 2),
-sum_b / (n as i64 - 2),
&ignore_idx,
);
for &(i, j) in &ans {
operatioin(i, j, &mut ab);
}
let mut ans_dist = i64::MAX;
let mut best_ans: Vec<(usize, usize)> = vec![];
ignore_idx.insert(0);
//while !timer.isTimeOver() {
for _ in 0..1 {
// 乱数要素を思いついたらtimerに戻す
let mut ab_new = ab.clone();
let mut ans_tmp = vec![];
let mut ignore_idx_tmp = ignore_idx.clone();
while ignore_idx_tmp.len() < n && (ans.len() + ans_tmp.len() <= 45) {
let (op, i) = solver6_mini2(n, &ab_new, -&ab_new[0].0, -&ab_new[0].1, &ignore_idx_tmp);
for (j, k) in op {
ans_tmp.push((j, k));
operatioin(j, k, &mut ab_new);
}
ignore_idx_tmp.insert(i);
// if ignore_idx_tmp.len() >= 30{
// ignore_idx_tmp = ignore_idx.clone();
// }
// eprintln!("{:?}", ignore_idx_tmp);
// eprintln!("{:?}", ans_tmp);
}
// 最後に反対側にいい感じのを作って0と合わせる
let (op, i) = solver6_mini2(n, &ab_new, -&ab_new[0].0, -&ab_new[0].1, &ignore_idx);
for (j, k) in op {
ans_tmp.push((j, k));
operatioin(j, k, &mut ab_new);
}
ans_tmp.push((0, i));
operatioin(0, i, &mut ab_new);
let dist = &ab_new[0].0.abs() + &ab_new[0].1.abs();
if dist < ans_dist {
ans_dist = dist;
best_ans = ans_tmp;
}
}
ans.append(&mut best_ans);
ans
}
fn main() {
input! {
n:usize,
ab:[(i64, i64); n]
}
// solve
let ans = solver7(n, ab.clone());
eprintln!("{}", calc_score(ab.clone(), &ans));
println!("{}", ans.len());
for &(u, v) in &ans {
println!("{} {}", u + 1, v + 1);
}
}
// ------------------------------------------
// 以下ライブラリ
// ------------------------------------------
// https://zenn.dev/tipstar0125/articles/245bceec86e40a
struct TimeKeeper {
t_start: std::time::Instant,
t_threshold: f64,
}
impl TimeKeeper {
fn new(t_threshold: f64) -> Self {
TimeKeeper {
t_start: std::time::Instant::now(),
t_threshold,
}
}
#[inline]
fn isTimeOver(&self) -> bool {
let elapsed_time = self.t_start.elapsed().as_nanos() as f64 * 1e-9;
#[cfg(feature = "local")]
{
elapsed_time * 0.85 >= self.t_threshold
}
#[cfg(not(feature = "local"))]
{
elapsed_time >= self.t_threshold
}
}
}
// XorShift
// Generated by Gemini
struct XorShift32 {
state: u32,
}
impl XorShift32 {
// 初期シード
fn new(seed: u32) -> Self {
XorShift32 {
state: if seed == 0 { 417553 } else { seed },
}
}
// 関数を呼び出すコードを、その関数の中身（本体）で直接置き換える
// 小さい処理を大量に呼び出す場合につけるとよい
#[inline]
// 次の乱数を生成
fn next_u32(&mut self) -> u32 {
let mut x = self.state;
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
self.state = x;
x
}
// Gemini君に作ってもらった
fn next_bool_u8(&mut self) -> u8 {
(self.next_u32() & 1) as u8
}
// 多分wataさんから引用
pub fn next_u64(&mut self) -> u64 {
((self.next_u32() as u64) << 32) | (self.next_u32() as u64)
}
// 多分wataさんから引用
pub fn next_f64(&mut self) -> f64 {
self.next_u32() as f64 / (u32::MAX as f64 + 1.0)
}
// usizeの範囲生成, u32の範囲で十分, [l, r]
fn next_range_usize(&mut self, l: usize, r: usize) -> usize {
debug_assert!(l <= r);
(self.next_u32() as usize % (r - l + 1)) + l
}
}