結果
| 問題 | No.2092 Conjugation |
| ユーザー |
 Moss_Local
|
| 提出日時 | 2022-10-07 21:24:07 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 18 ms / 2,000 ms |
| コード長 | 17,417 bytes |
| コンパイル時間 | 13,954 ms |
| コンパイル使用メモリ | 382,608 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-06-12 05:48:21 |
| 合計ジャッジ時間 | 15,638 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
5,248 KB |
| testcase_01 | AC | 1 ms
5,376 KB |
| testcase_02 | AC | 1 ms
5,376 KB |
| testcase_03 | AC | 1 ms
6,816 KB |
| testcase_04 | AC | 1 ms
6,944 KB |
| testcase_05 | AC | 1 ms
6,940 KB |
| testcase_06 | AC | 1 ms
6,944 KB |
| testcase_07 | AC | 12 ms
6,944 KB |
| testcase_08 | AC | 15 ms
6,940 KB |
| testcase_09 | AC | 13 ms
6,944 KB |
| testcase_10 | AC | 14 ms
6,944 KB |
| testcase_11 | AC | 14 ms
6,940 KB |
| testcase_12 | AC | 13 ms
6,944 KB |
| testcase_13 | AC | 13 ms
6,944 KB |
| testcase_14 | AC | 12 ms
6,944 KB |
| testcase_15 | AC | 13 ms
6,944 KB |
| testcase_16 | AC | 16 ms
6,944 KB |
| testcase_17 | AC | 18 ms
6,940 KB |
| testcase_18 | AC | 17 ms
6,940 KB |
| testcase_19 | AC | 3 ms
6,940 KB |
コンパイルメッセージ
warning: unnecessary parentheses around type
--> src/main.rs:85:15
|
85 | fn readi() -> (i64) {
| ^ ^
|
= note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
|
85 - fn readi() -> (i64) {
85 + fn readi() -> i64 {
|
warning: variable does not need to be mutable
--> src/main.rs:609:9
|
609 | let mut vec: Vec<usize> = read_vec();
| ----^^^
| |
| help: remove this `mut`
|
= note: `#[warn(unused_mut)]` on by default
warning: variable `X` should have a snake case name
--> src/main.rs:332:13
|
332 | let X = x * (a2 * (b2 + c2 - a2)) + y * (b2 * (c2 + a2 - b2)) + z * (c2 * (a2 + b2 - c2));
| ^ help: convert the identifier to snake case (notice the capitalization): `x`
|
= note: `#[warn(non_snake_case)]` on by default
warning: variable `Y` should have a snake case name
--> src/main.rs:333:13
|
333 | let Y = a2 * (b2 + c2 - a2) + b2 * (c2 + a2 - b2) + c2 * (a2 + b2 - c2);
| ^ help: convert the identifier to snake case (notice the capitalization): `y`
ソースコード
// -*- coding:utf-8-unix -*-
// #![feature(map_first_last)]
#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_macros)]
use core::num;
use std::any::Any;
use std::cmp::Ordering::*;
use std::collections::btree_map::Values;
use std::collections::*;
use std::convert::*;
use std::convert::{From, Into};
use std::error::Error;
use std::f32::consts::E;
use std::fmt::Debug;
use std::fmt::Display;
use std::fs::File;
use std::hash::Hash;
use std::io::prelude::*;
use std::io::*;
use std::iter::Filter;
use std::iter::FromIterator;
use std::marker::Copy;
use std::mem::*;
use std::ops::BitAnd;
use std::ops::Bound::*;
use std::ops::RangeBounds;
use std::ops::{Add, Mul, Neg, Sub};
use std::process;
use std::slice::from_raw_parts;
use std::str;
use std::vec;
const INF: i64 = 1223372036854775807;
const UINF: usize = INF as usize;
const LINF: i64 = 2147483647;
const INF128: i128 = 1223372036854775807000000000000;
const MOD: i64 = 1000000007;
// const MOD: i64 = 998244353;
const UMOD: usize = MOD as usize;
const M_PI: f64 = 3.14159265358979323846;
// const MOD: i64 = INF;
use std::cmp::*;
use std::collections::*;
use std::io::stdin;
use std::io::stdout;
use std::io::Write;
macro_rules! p {
($x:expr) => {
println!("{}", $x);
};
}
macro_rules! d {
($x:expr) => {
println!("{:?}", $x);
};
}
#[allow(unused_macros)]
pub mod macros {
macro_rules! min { ($x: expr) => { $x }; ($x: expr, $($xs: expr),+) => {{ let y = macros::min!($($xs),+); std::cmp::min($x, y) } }}
macro_rules! max { ($x: expr) => { $x }; ($x: expr, $($xs: expr),+) => {{ let y = macros::max!($($xs),+); std::cmp::max($x, y) } }}
macro_rules! chmin { ($x: expr, $($xs: expr),+) => {{ let y = macros::min!($($xs),+); if $x > y { $x = y; true } else { false } }}}
macro_rules! chmax { ($x: expr, $($xs: expr),+) => {{ let y = macros::max!($($xs),+); if $x < y { $x = y; true } else { false } }}}
macro_rules! multi_vec { ($element: expr; ($len: expr, $($lens: expr),*)) => ( vec![macros::multi_vec![$element; ($($lens),*)]; $len] ); ($element: expr; ($len: expr)) => ( vec![$element; $len] ); }
macro_rules! multi_box_array { ($element: expr; ($len: expr, $($lens: expr),*)) => ( vec![macros::multi_box_array![$element; ($($lens),*)]; $len].into_boxed_slice() ); ($element: expr; ($len: expr)) => ( vec![$element; $len].into_boxed_slice() ); }
#[allow(unused_imports)]
pub(super) use {chmax, chmin, max, min, multi_box_array, multi_vec};
}
fn main() {
solve();
}
// use str::Chars;
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
let mut s = String::new();
std::io::stdin().read_line(&mut s).ok();
s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn readi() -> (i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
iter.next().unwrap().parse::<i64>().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
read::<String>()
.split_whitespace()
.map(|e| e.parse().ok().unwrap())
.collect()
}
#[allow(dead_code)]
fn read_mat<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
(0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn readii() -> (i64, i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
)
}
#[allow(dead_code)]
fn readiii() -> (i64, i64, i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
)
}
#[allow(dead_code)]
fn readuu() -> (usize, usize) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
)
}
#[allow(dead_code)]
fn readff() -> (f64, f64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<f64>().unwrap(),
iter.next().unwrap().parse::<f64>().unwrap(),
)
}
fn readcc() -> (char, char) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<char>().unwrap(),
iter.next().unwrap().parse::<char>().unwrap(),
)
}
fn readuuu() -> (usize, usize, usize) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
)
}
#[allow(dead_code)]
fn readiiii() -> (i64, i64, i64, i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
)
}
use std;
const EPS: f64 = 1e-9;
#[derive(Debug, Clone, Copy)]
#[allow(dead_code)]
pub struct Vector2D(f64, f64);
impl Vector2D {
pub fn add(a: f64, b: f64) -> f64 {
let c = a + b;
if c.abs() < EPS {
0.0
} else {
c
}
}
pub fn dot(self, other: Vector2D) -> f64 {
Self::add(self.0 * other.0, self.1 * other.1)
}
pub fn det(self, other: Vector2D) -> f64 {
Self::add(self.0 * other.1, -self.1 * other.0)
}
pub fn complex_mul(self, other: Vector2D) -> Self {
let real = self.0 * other.0 - self.1 * other.1;
let imag = self.0 * other.1 + self.1 * other.0;
Vector2D(real, imag)
}
pub fn dist(self, other: Self) -> f64 {
(self - other).len()
}
pub fn len(&self) -> f64 {
f64::sqrt((self.0).powi(2) + (self.1).powi(2))
}
pub fn unit(self) -> Vector2D {
let l = self.len();
Vector2D(self.0 / l, self.1 / l)
}
#[doc = "orthogonal vector"]
pub fn normal(self) -> Vector2D {
Vector2D(self.1, -self.0).unit()
}
#[doc = "bisection of the angle"]
pub fn bisect(a: Vector2D, b: Vector2D) -> Vector2D {
(a.unit() + b.unit()).unit()
}
}
impl std::ops::Add for Vector2D {
type Output = Vector2D;
fn add(self, rhs: Vector2D) -> Self::Output {
Vector2D(Vector2D::add(self.0, rhs.0), Vector2D::add(self.1, rhs.1))
}
}
impl std::ops::Sub for Vector2D {
type Output = Vector2D;
fn sub(self, rhs: Vector2D) -> Self::Output {
Vector2D(Vector2D::add(self.0, -rhs.0), Vector2D::add(self.1, -rhs.1))
}
}
impl std::ops::Mul<f64> for Vector2D {
type Output = Vector2D;
fn mul(self, rhs: f64) -> Self::Output {
Vector2D(rhs * self.0, rhs * self.1)
}
}
impl std::ops::Div<f64> for Vector2D {
type Output = Vector2D;
fn div(self, rhs: f64) -> Self::Output {
Vector2D(self.0 / rhs, self.1 / rhs)
}
}
impl std::cmp::PartialEq for Vector2D {
fn eq(&self, other: &Self) -> bool {
let x = (self.0 - other.0).abs();
let y = (self.1 - other.1).abs();
x < EPS && y < EPS
}
}
#[derive(Clone, Copy)]
struct Triangle {
x: Vector2D,
y: Vector2D,
z: Vector2D,
}
impl Triangle {
pub fn exists(&self) -> bool {
let a = (self.y - self.z).len();
let b = (self.x - self.z).len();
let c = (self.x - self.y).len();
if a + b - c < EPS {
return false;
}
if b + c - a < EPS {
return false;
}
if c + a - b < EPS {
return false;
}
true
}
}
#[derive(Debug, Clone, Copy)]
pub struct Circle {
center: Vector2D,
radius: f64,
}
impl Circle {
pub fn inner_circle(a: Vector2D, b: Vector2D, c: Vector2D) -> Option<Circle> {
let tri = Triangle { x: a, y: b, z: c };
if !tri.exists() {
return None;
}
let a_bisect = Line2D::pd(a, Vector2D::bisect(a - b, a - c));
let b_bisect = Line2D::pd(b, Vector2D::bisect(b - a, b - c));
let center = Line2D::intersection(a_bisect, b_bisect);
let ab = Line2D::pd(a, b - a);
let radius = ab.distance(center);
Some(Circle {
center: center,
radius: radius,
})
}
pub fn outer_circle(x: Vector2D, y: Vector2D, z: Vector2D) -> Option<Circle> {
let a = (y - z).len();
let a2 = a * a;
let b = (x - z).len();
let b2 = b * b;
let c = (x - y).len();
let c2 = c * c;
if a + b - c < EPS {
return None;
}
if b + c - a < EPS {
return None;
}
if c + a - b < EPS {
return None;
}
let X = x * (a2 * (b2 + c2 - a2)) + y * (b2 * (c2 + a2 - b2)) + z * (c2 * (a2 + b2 - c2));
let Y = a2 * (b2 + c2 - a2) + b2 * (c2 + a2 - b2) + c2 * (a2 + b2 - c2);
let center = X / Y;
let radius = (x - center).len();
Some(Circle {
center: center,
radius: radius,
})
}
pub fn intersection(c1: &Self, c2: &Self) -> Vec<Vector2D> {
let d = c1.center.dist(c2.center);
if d > c1.radius + c2.radius + EPS {
return vec![];
}
if c1.center == c2.center {
return vec![];
}
let rc: f64 = (d * d + c1.radius * c1.radius - c2.radius * c2.radius) / (2. * d);
let rs: f64 = f64::sqrt(c1.radius * c1.radius - rc * rc);
let diff: Vector2D = (c2.center - c1.center) / d;
let p1 = c1.center + diff.complex_mul(Vector2D(rc, rs));
let p2 = c1.center + diff.complex_mul(Vector2D(rc, -rs));
if p1 == p2 {
vec![p1]
} else {
vec![p1, p2]
}
}
}
#[test]
fn test_inner_circle() {
let p1 = Vector2D(0., 0.);
let p2 = Vector2D(0., 1.);
let p3 = Vector2D(1., 0.);
let ic = Circle::inner_circle(p1, p2, p1);
dbg!(&ic);
let ic = Circle::inner_circle(p1, p2, p3);
dbg!(&ic);
}
#[test]
fn test_outer_circle() {
let p1 = Vector2D(0., 0.);
let p2 = Vector2D(0., 1.);
let p3 = Vector2D(1., 0.);
let ic = Circle::outer_circle(p1, p2, p1);
dbg!(&ic);
let ic = Circle::outer_circle(p1, p2, p3);
dbg!(&ic);
}
#[test]
fn test_circle_intersection() {
let c1 = Circle {
center: Vector2D(1., 0.),
radius: 2.,
};
let c2 = Circle {
center: Vector2D(-1., 0.),
radius: 2.,
};
dbg!(Circle::intersection(&c1, &c1));
dbg!(Circle::intersection(&c1, &c2));
let c1 = Circle {
center: Vector2D(1., 0.),
radius: 1.,
};
let c2 = Circle {
center: Vector2D(-1., 0.),
radius: 1.,
};
dbg!(Circle::intersection(&c1, &c2));
let c1 = Circle {
center: Vector2D(1., 0.),
radius: 0.8,
};
let c2 = Circle {
center: Vector2D(-1., 0.),
radius: 0.8,
};
dbg!(Circle::intersection(&c1, &c2));
}
/// Is line a-b and line c-d intersected ?
pub fn is_intersected(a: Vector2D, b: Vector2D, c: Vector2D, d: Vector2D) -> bool {
let ta = (c.0 - d.0) * (a.1 - c.1) + (c.1 - d.1) * (c.0 - a.0);
let tb = (c.0 - d.0) * (b.1 - c.1) + (c.1 - d.1) * (c.0 - b.0);
let tc = (a.0 - b.0) * (c.1 - a.1) + (a.1 - b.1) * (a.0 - c.0);
let td = (a.0 - b.0) * (d.1 - a.1) + (a.1 - b.1) * (a.0 - d.0);
tc * td <= 0.0 && ta * tb <= 0.0
// Not intersects start or end point.
// tc * td < 0.0 && ta * tb < 0.0
}
#[derive(Clone, Copy, Debug)]
pub struct Line2D {
p: Vector2D,
d: Vector2D,
}
impl Line2D {
pub fn pd(p: Vector2D, d: Vector2D) -> Self {
Line2D { p: p, d: d.unit() }
}
pub fn from_two_points(a: Vector2D, b: Vector2D) -> Self {
Line2D { p: a, d: b - a }
}
pub fn intersection(a: Line2D, b: Line2D) -> Vector2D {
let n = b.d.normal();
let x = n.dot(b.p - a.p) / n.dot(a.d);
a.p + a.d * x
}
pub fn distance(self, a: Vector2D) -> f64 {
let perpendicular = Self::pd(a, self.d.normal());
let q = Self::intersection(self, perpendicular);
(a - q).len()
}
}
#[test]
fn test_line_intersection() {
let m = Line2D::pd(Vector2D(0., 0.), Vector2D(1., 1.));
let l1 = Line2D::pd(Vector2D(0., 2.), Vector2D(1., 0.));
let l2 = Line2D::pd(Vector2D(0., 2.), Vector2D(1., -1.));
let p1 = Line2D::intersection(m, l1);
let p2 = Line2D::intersection(m, l2);
assert_eq!(p1, Vector2D(2., 2.));
assert_eq!(p2, Vector2D(1., 1.));
}
#[test]
fn test_line_distance() {
let l = Line2D::from_two_points(Vector2D(-1., 1.), Vector2D(1., 1.));
let p = Vector2D(0., 0.);
assert_eq!(l.distance(p), 1.);
}
#[derive(PartialEq, PartialOrd)]
/// Implement Eq and Ord for a type which has only PartialEq and PartialOrd.
/// It is useful when sorting a Vec of f64
pub struct Total<T>(pub T);
impl<T: PartialEq> Eq for Total<T> {}
impl<T: PartialOrd> Ord for Total<T> {
fn cmp(&self, other: &Total<T>) -> Ordering {
self.0.partial_cmp(&other.0).unwrap()
}
}
#[allow(dead_code)]
fn convex_hull(vs: &[Vector2D]) -> Vec<usize> {
let mut idx: Vec<usize> = (0..vs.len()).collect();
idx.sort_by_key(|&i| Total((vs[i].0, vs[i].1)));
let mut res = Vec::new();
for &i in &idx {
while res.len() > 1
&& Vector2D::det(
vs[res[res.len() - 1]] - vs[res[res.len() - 2]],
vs[i] - vs[res[res.len() - 1]],
) <= 0.0
{
res.pop();
}
res.push(i);
}
let t = res.len();
for &i in idx.iter().rev().skip(1) {
while res.len() > t
&& (vs[res[res.len() - 1]] - vs[res[res.len() - 2]]).det(vs[i] - vs[res[res.len() - 1]])
<= 0.0
{
res.pop();
}
res.push(i);
}
res.pop();
res
}
#[test]
fn test_convex_hull() {
let vs = vec![
Vector2D(-1.0, -1.0),
Vector2D(-1.0, 1.0),
Vector2D(1.0, 1.0),
Vector2D(1.0, -1.0),
Vector2D(0.0, 0.0),
Vector2D(0.1, 0.1),
];
let mut idx = convex_hull(&vs);
idx.sort();
assert_eq!(&idx, &[0, 1, 2, 3]);
}
pub fn closest_pair(ps: &[(f64, f64)]) -> ((f64, f64), (f64, f64)) {
fn d(p1: (f64, f64), p2: (f64, f64)) -> f64 {
((p1.0 - p2.0).powi(2) + (p1.1 - p2.1).powi(2)).sqrt()
}
fn rec(x_sort: &[(f64, f64)], y_sort: &[(f64, f64)]) -> ((f64, f64), (f64, f64)) {
if x_sort.len() <= 3 {
let mut min_d = std::f64::MAX;
let mut pair = ((0.0, 0.0), (0.0, 0.0));
for (i, &p1) in x_sort.iter().enumerate() {
for (j, &p2) in x_sort.iter().enumerate() {
if i != j {
let dist = d(p1, p2);
if dist < min_d {
min_d = dist;
pair = (p1, p2);
}
}
}
}
return pair;
}
let mid = x_sort.len() / 2;
let pivot = x_sort[mid].0;
let q_x = &x_sort[..mid];
let r_x = &x_sort[mid..];
let mut q_y = Vec::with_capacity(mid);
let mut r_y = Vec::with_capacity(x_sort.len() - mid);
for &(x, y) in y_sort {
if x < pivot {
q_y.push((x, y));
} else {
r_y.push((x, y));
}
}
let pair1 = rec(q_x, &q_y);
let pair2 = rec(r_x, &r_y);
let w = d(pair1.0, pair1.1).min(d(pair2.0, pair2.1));
let s: Vec<(f64, f64)> = y_sort
.iter()
.filter(|&&(x, _)| (pivot - x).abs() <= w)
.cloned()
.collect();
let mut min_d = w;
let mut pair = if d(pair1.0, pair1.1) < d(pair2.0, pair2.1) {
pair1
} else {
pair2
};
for (i, &p1) in s.iter().enumerate() {
for &p2 in s[i + 1..].iter().take(15) {
let dist = d(p1, p2);
if dist < min_d {
min_d = dist;
pair = (p1, p2);
}
}
}
pair
}
let mut x_sort = ps.to_vec();
let mut y_sort = ps.to_vec();
x_sort.sort_by_key(|p| Total(p.0));
y_sort.sort_by_key(|p| Total(p.1));
rec(&x_sort, &y_sort)
}
fn solve() {
let n: usize = read();
let mut vec: Vec<usize> = read_vec();
let mut res = vec![0; 101010];
for i in 0..n {
res[0] += 1;
res[vec[i]] -= 1;
}
for i in 0..101000 {
res[i + 1] += res[i];
}
for i in 0..vec[0] {
if i != 0 {
print!(" ");
}
print!("{}", res[i]);
}
println!("");
return;
}