Submission #73089382

---

Source Code Expand

use proconio::input;

#[allow(non_snake_case)]
fn main() {
    input! {
        N: usize,
        mut A: [i64; N],
    }

    A.sort();

    let sum_A: i64 = A.iter().sum();
    let max_A = A[N - 1];
    // 本数 M → N
    let min_M = (N + 1) / 2;
    let max_M = N;

    let mut candidate_Ls = Vec::new();
    let mut d = 1i64; // divisor
    while d * d <= sum_A {
        if sum_A % d == 0 {
            let L1 = d;
            let M1 = sum_A / L1;
            if M1 >= min_M as i64 && M1 <= max_M as i64 && L1 >= max_A {
                candidate_Ls.push(L1);
            }

            let L2 = sum_A / d;
            if L2 != L1 {
                let M2 = d;
                if M2 >= min_M as i64 && M2 <= max_M as i64 && L2 >= max_A {
                    candidate_Ls.push(L2);
                }
            }
        }
        d += 1;
    }

    let mut valid_Ls = Vec::new();
    for &L in &candidate_Ls {
        if is_valid(&A, L) {
            valid_Ls.push(L);
        }
    }

    valid_Ls.sort();
    valid_Ls.dedup();

    println!("{}", valid_Ls.iter().map(|x| x.to_string()).collect::<Vec<_>>().join(" "));
}

#[allow(non_snake_case)]
fn is_valid(A: &[i64], L: i64) -> bool {
    let N = A.len();
    let mut left = 0;
    let mut right = N - 1;

    while left < right {
        if A[right] == L {
            right -= 1;
        } else if A[right] < L {
            let need = L - A[right];
            if A[left] != need {
                return false;
            }
            left += 1;
            right -= 1;
        } else {
            return false;
        }
    }

    if left == right && A[left] != L {
        return false;
    }

    true
}

Submission Info

Judge Result