#676992 (Rust) No.1594 Three Classes

• 問題: No.1594 Three Classes
• ユーザー: c--
• 提出日時: 2021-07-10 11:16:03
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 74 ms / 2,000 ms
• コード長: 13,140 bytes
• コンパイル時間: 18,957 ms
• コンパイル使用メモリ: 378,540 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-07-02 01:51:22
• 合計ジャッジ時間: 15,240 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	74 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	3 ms; 5,376 KB
testcase_04	AC	72 ms; 5,376 KB
testcase_05	AC	74 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	4 ms; 5,376 KB
testcase_08	AC	72 ms; 5,376 KB
testcase_09	AC	71 ms; 5,376 KB
testcase_10	AC	72 ms; 5,376 KB
testcase_11	AC	73 ms; 5,376 KB
testcase_12	AC	74 ms; 5,376 KB
testcase_13	AC	1 ms; 5,376 KB
testcase_14	AC	16 ms; 5,376 KB
testcase_15	AC	10 ms; 5,376 KB
testcase_16	AC	5 ms; 5,376 KB
testcase_17	AC	4 ms; 5,376 KB
testcase_18	AC	1 ms; 5,376 KB
testcase_19	AC	2 ms; 5,376 KB
testcase_20	AC	1 ms; 5,376 KB

ソースコード

#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_mut)]
#![allow(unused_macros)]
#![allow(unused_variables)]
#![allow(non_upper_case_globals)]
#![allow(non_snake_case)]
// use itertools::Itertools;
// use proconio::{fastout, input, marker::*};
use proconio::{input, marker::*};
use std::cmp::*;
use std::collections::*;
use std::num::*;
use std::process::exit;

const dydx: [(i64, i64); 4] = [(-1, 0), (0, 1), (1, 0), (0, -1)];
const INF: usize = usize::max_value();
const IINF: i64 = i64::max_value();
const MOD1: usize = 1_000_000_007;
const MOD2: usize = 998_244_353;

/// Algebra - ModInt (Zp)
#[derive(Debug, PartialEq, Eq, Clone, Copy)]
pub struct ModInt(pub i64, pub i64); // (residual, modulo)

pub const MOD_1000000007: i64 = 1_000_000_007;
pub const MOD_998244353: i64 = 998_244_353;

impl ModInt {
    pub fn new(residual: i64, modulo: i64) -> ModInt {
        if residual >= modulo {
            ModInt(residual % modulo, modulo)
        } else if residual < 0 {
            ModInt((residual % modulo) + modulo, modulo)
        } else {
            ModInt(residual, modulo)
        }
    }
    pub fn unwrap(self) -> i64 {
        self.0
    }
    pub fn inv(self) -> Self {
        fn exgcd(r0: i64, a0: i64, b0: i64, r: i64, a: i64, b: i64) -> (i64, i64, i64) {
            if r > 0 {
                exgcd(r, a, b, r0 % r, a0 - r0 / r * a, b0 - r0 / r * b)
            } else {
                (a0, b0, r0)
            }
        }
        let (a, _, r) = exgcd(self.0, 1, 0, self.1, 0, 1);
        if r != 1 {
            panic!("{:?} has no inverse!", self);
        }
        ModInt(((a % self.1) + self.1) % self.1, self.1)
    }
    pub fn pow(self, n: i64) -> Self {
        if n < 0 {
            self.pow(-n).inv()
        } else if n == 0 {
            ModInt(1, self.1)
        } else if n == 1 {
            self
        } else {
            let mut x = (self * self).pow(n / 2);
            if n % 2 == 1 {
                x *= self
            }
            x
        }
    }
}
impl std::fmt::Display for ModInt {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}
impl std::ops::Neg for ModInt {
    type Output = Self;
    fn neg(self) -> Self {
        if self.0 == 0 {
            return self;
        }
        ModInt(self.1 - self.0, self.1)
    }
}
impl std::ops::Add<i64> for ModInt {
    type Output = Self;
    fn add(self, other: i64) -> Self {
        ModInt::new(self.0 + other, self.1)
    }
}
impl std::ops::Add for ModInt {
    type Output = Self;
    fn add(self, other: ModInt) -> Self {
        self + other.0
    }
}
impl std::ops::Add<ModInt> for i64 {
    type Output = ModInt;
    fn add(self, other: ModInt) -> ModInt {
        other + self
    }
}
impl std::ops::AddAssign<i64> for ModInt {
    fn add_assign(&mut self, other: i64) {
        self.0 = ModInt::new(self.0 + other, self.1).0;
    }
}
impl std::ops::AddAssign for ModInt {
    fn add_assign(&mut self, other: ModInt) {
        *self += other.0;
    }
}
impl std::ops::Sub<i64> for ModInt {
    type Output = Self;
    fn sub(self, other: i64) -> Self {
        ModInt::new(self.0 - other, self.1)
    }
}
impl std::ops::Sub for ModInt {
    type Output = Self;
    fn sub(self, other: ModInt) -> Self {
        self - other.0
    }
}
impl std::ops::Sub<ModInt> for i64 {
    type Output = ModInt;
    fn sub(self, other: ModInt) -> ModInt {
        ModInt::new(self - other.0, other.1)
    }
}
impl std::ops::SubAssign<i64> for ModInt {
    fn sub_assign(&mut self, other: i64) {
        self.0 = ModInt::new(self.0 - other, self.1).0;
    }
}
impl std::ops::SubAssign for ModInt {
    fn sub_assign(&mut self, other: ModInt) {
        *self -= other.0;
    }
}
impl std::ops::Mul<i64> for ModInt {
    type Output = Self;
    fn mul(self, other: i64) -> Self {
        ModInt::new(self.0 * other, self.1)
    }
}
impl std::ops::Mul for ModInt {
    type Output = Self;
    fn mul(self, other: ModInt) -> Self {
        self * other.0
    }
}
impl std::ops::Mul<ModInt> for i64 {
    type Output = ModInt;
    fn mul(self, other: ModInt) -> ModInt {
        other * self
    }
}
impl std::ops::MulAssign<i64> for ModInt {
    fn mul_assign(&mut self, other: i64) {
        self.0 = ModInt::new(self.0 * other, self.1).0;
    }
}
impl std::ops::MulAssign for ModInt {
    fn mul_assign(&mut self, other: ModInt) {
        *self *= other.0;
    }
}
impl std::ops::Div for ModInt {
    type Output = Self;
    fn div(self, other: ModInt) -> Self {
        self * other.inv()
    }
}
impl std::ops::Div<i64> for ModInt {
    type Output = Self;
    fn div(self, other: i64) -> Self {
        self / ModInt::new(other, self.1)
    }
}
impl std::ops::Div<ModInt> for i64 {
    type Output = ModInt;
    fn div(self, other: ModInt) -> ModInt {
        other.inv() * self
    }
}
impl std::ops::DivAssign for ModInt {
    fn div_assign(&mut self, other: ModInt) {
        self.0 = (*self / other).0;
    }
}
impl std::ops::DivAssign<i64> for ModInt {
    fn div_assign(&mut self, other: i64) {
        *self /= ModInt(other, self.1);
    }
}
#[macro_export]
macro_rules! mint {
    ($x:expr) => {
        ModInt::new($x, MOD_1000000007)
    };
}
impl std::iter::Sum for ModInt {
    fn sum<I>(iter: I) -> Self
    where
        I: Iterator<Item = ModInt>,
    {
        let mut r = mint!(0);
        for x in iter {
            r = r + x
        }
        r
    }
}

/// Implement (union by size) + (path compression)
/// Reference:
/// Zvi Galil and Giuseppe F. Italiano,
/// Data structures and algorithms for disjoint set union problems
pub struct Dsu {
    n: usize,
    // root node: -1 * component size
    // otherwise: parent
    parent_or_size: Vec<i32>,
}

impl Dsu {
    // 0 <= size <= 10^8 is constrained.
    pub fn new(size: usize) -> Self {
        Self {
            n: size,
            parent_or_size: vec![-1; size],
        }
    }
    pub fn merge(&mut self, a: usize, b: usize) -> usize {
        assert!(a < self.n);
        assert!(b < self.n);
        let (mut x, mut y) = (self.leader(a), self.leader(b));
        if x == y {
            return x;
        }
        if -self.parent_or_size[x] < -self.parent_or_size[y] {
            std::mem::swap(&mut x, &mut y);
        }
        self.parent_or_size[x] += self.parent_or_size[y];
        self.parent_or_size[y] = x as i32;
        x
    }

    pub fn same(&mut self, a: usize, b: usize) -> bool {
        assert!(a < self.n);
        assert!(b < self.n);
        self.leader(a) == self.leader(b)
    }
    pub fn leader(&mut self, a: usize) -> usize {
        assert!(a < self.n);
        if self.parent_or_size[a] < 0 {
            return a;
        }
        self.parent_or_size[a] = self.leader(self.parent_or_size[a] as usize) as i32;
        self.parent_or_size[a] as usize
    }
    pub fn size(&mut self, a: usize) -> usize {
        assert!(a < self.n);
        let x = self.leader(a);
        -self.parent_or_size[x] as usize
    }
    pub fn groups(&mut self) -> Vec<Vec<usize>> {
        let mut leader_buf = vec![0; self.n];
        let mut group_size = vec![0; self.n];
        for i in 0..self.n {
            leader_buf[i] = self.leader(i);
            group_size[leader_buf[i]] += 1;
        }
        let mut result = vec![Vec::new(); self.n];
        for i in 0..self.n {
            result[i].reserve(group_size[i]);
        }
        for i in 0..self.n {
            result[leader_buf[i]].push(i);
        }
        result
            .into_iter()
            .filter(|x| !x.is_empty())
            .collect::<Vec<Vec<usize>>>()
    }
}

fn lcm(a: usize, b: usize) -> usize {
    a / gcd(a, b) * b
}

fn gcd(a: usize, b: usize) -> usize {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

fn nck(n: usize, k: usize) -> usize {
    let mut x = 1;
    for i in 0..k {
        x *= n - i;
        x /= 1 + i;
    }
    return x;
}

fn make_divisors(n: usize) -> Vec<usize> {
    let mut lower_divisors = vec![];
    let mut upper_divisors = vec![];
    let mut i = 1;
    while (i * i) <= n {
        if n % i == 0 {
            lower_divisors.push(i);
            if i != n / i {
                upper_divisors.push(n / i);
            }
        }
        i += 1;
    }
    lower_divisors.append(&mut upper_divisors);
    return lower_divisors;
}

fn prime_factorize(mut n: usize) -> Vec<usize> {
    let mut v = vec![];
    while n % 2 == 0 {
        v.push(2);
        n /= 2;
    }
    let mut f = 3;
    while f * f <= n {
        if n % f == 0 {
            v.push(f);
            n /= f;
        } else {
            f += 2;
        }
    }
    if n != 1 {
        v.push(n);
    }
    return v;
}

fn is_prime(x: usize) -> bool {
    if x < 2 {
        return false;
    }
    if x == 2 || x == 3 || x == 5 {
        return true;
    }
    if x % 2 == 0 || x % 3 == 0 || x % 5 == 0 {
        return false;
    }
    let mut prime = 7.;
    let mut step = 4.;
    while prime <= (x as f64).sqrt() {
        if x as f64 % prime == 0. {
            return false;
        }
        prime += step;
        step = 6. - step;
    }

    return true;
}

fn prime_factorize_count(n: usize) -> HashMap<usize, usize> {
    let mut prime_facts = prime_factorize(n);
    let mut facts = HashMap::<usize, usize>::new();
    for &j in &prime_facts {
        *facts.entry(j).or_insert(0) += 1;
    }
    return facts;
}

pub trait BinarySearch<T> {
    fn lower_bound(&self, x: &T) -> usize;
    fn upper_bound(&self, x: &T) -> usize;
}

impl<T: Ord> BinarySearch<T> for [T] {
    fn lower_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                Ordering::Less => {
                    low = mid + 1;
                }
                Ordering::Equal | Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }

    fn upper_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                Ordering::Less | Ordering::Equal => {
                    low = mid + 1;
                }
                Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }
}

macro_rules! chmin {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_min = min!($($cmps),+);
        if $base > cmp_min {
            $base = cmp_min;
            true
        } else {
            false
        }
    }};
}

macro_rules! chmax {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_max = max!($($cmps),+);
        if $base < cmp_max {
            $base = cmp_max;
            true
        } else {
            false
        }
    }};
}

macro_rules! min {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::min($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::min($a, min!($($rest),+))
    }};
}

macro_rules! max {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::max($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::max($a, max!($($rest),+))
    }};
}
// nck mod p
// const MAX: usize = 1000000;
// const MOD: usize = MOD1;

// let mut fac: Vec<usize> = vec![0; MAX + 1];
// let mut finv: Vec<usize> = vec![0; MAX + 1];
// let mut inv: Vec<usize> = vec![0; MAX + 1];

// let cominit = {
//     for i in 0..=1 {
//         fac[i] = 1;
//         finv[i] = 1;
//     }
//     inv[1] = 1;
//     for i in 2..MAX {
//         fac[i] = fac[i - 1] * i % MOD;
//         inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
//         finv[i] = finv[i - 1] * inv[i] % MOD;
//     }
// };

// let com = |n: usize, k: usize| -> usize {
//     return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
// };

macro_rules! dd {
    ($($a:expr),* $(,)*) => {
        #[cfg(debug_assertions)]
        eprintln!(concat!($("| ", stringify!($a), " = {:?} "),*, "|"), $(&$a),*);
    };
}

macro_rules! p {
    ($x:expr) => {
        println!("{}", $x);
    };
}

macro_rules! pp {
    ($x:expr) => {
        println!("{:?}", $x);
    };
}

//////////////////////////////////////////////////////////////
//
//////////////////////////////////////////////////////////////
struct Env {}

impl Env {
    fn solve(&mut self) {}
}

// #[fastout]
fn main() {
    input! {
        n: usize,
        e: [usize; n],
    };

    let mut idx = vec![0; 15];
    for mask in 0..(3_i32.pow(n as u32)) {
        let mut tmp = mask;
        for i in 0..n {
            idx[i] = tmp as usize % 3;
            tmp /= 3;
        }
        let mut a = vec![0, 0, 0];
        for i in 0..n {
            a[idx[i]] += e[i];
        }

        let mut set = HashSet::new();
        for i in a {
            set.insert(i);
        }
        if set.len() == 1 {
            p!("Yes");
            return;
        }
    }

    p!("No");
}