Summat

warning: unused import: `std::collections::BTreeSet`
 --> input/code.rs:2:5
  |
2 | use std::collections::BTreeSet;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused variable: `n`
  --> input/code.rs:59:5
   |
59 |     n: usize,
   |     ^ help: consider prefixing with an underscore: `_n`
   |
   = note: `#[warn(unused_variables)]` on by default

use std::collections::BTreeMap;
use std::collections::BTreeSet;
use std::io::BufRead;
 
fn print_iter<I: Iterator>(iter: I)
where
    <I as Iterator>::Item: std::fmt::Display,
{
    let mut iter = iter;
    if let Some(v) = iter.next() {
        print!("{}", v);
        for v in iter {
            print!(" {}", v);
        }
    }
    println!();
}
 
struct Counter {
    counts: BTreeMap<usize, usize>,
}
 
impl Counter {
    pub fn new() -> Self {
        Self {
            counts: BTreeMap::new(),
        }
    }
 
    pub fn is_empty(&self) -> bool {
        self.counts.is_empty()
    }
 
    pub fn first(&self) -> usize {
        *self.counts.iter().next().unwrap().0
    }
 
    pub fn add(&mut self, val: usize) {
        *self.counts.entry(val).or_insert(0) += 1;
    }
 
    pub fn remove(&mut self, val: usize) -> bool {
        let count = self.counts.get_mut(&val);
        if let Some(count) = count {
            assert!(*count > 0);
            *count -= 1;
            if *count == 0 {
                self.counts.remove(&val);
            }
            true
        } else {
            false
        }
    }
}
 
fn solve_with_three_smallest(
    v: &[usize],
    n: usize,
    (a0, a1, a2): (usize, usize, usize),
) -> Option<Vec<usize>> {
    // println!("{}, {}, {}", a0, a1, a2);
 
    // What to do with tree smallest elements?
    let mut res = Vec::new();
    let mut left = Counter::new();
    for v in v {
        left.add(*v);
    }
 
    left.remove(a0 + a1);
    left.remove(a0 + a2);
    left.remove(a1 + a2);
    res.push(a0);
    res.push(a1);
    res.push(a2);
 
    // The next smallest element has to be a0+??
    while !left.is_empty() {
        let ai = left.first() - a0;
        for a in &res {
            if !left.remove(a + ai) {
                return None;
            }
        }
        res.push(ai);
    }
 
    Some(res)
}
 
fn solve(v: Vec<usize>, n: usize) -> Vec<usize> {
    assert_eq!(v.len(), n * (n - 1) / 2);
    let mut v = v;
    v.sort();
 
    // Guess the three smallest elements
    for i in 2..=(n + 3).min(v.len() - 1) {
        let v0 = v[0];
        let v1 = v[1];
        let vi = v[i];
        let a0 = (v0 + v1 - vi) / 2;
        let a1 = (v0 + vi - v1) / 2;
        let a2 = (v1 + vi - v0) / 2;
        if a0 + a1 == v0 && a0 + a2 == v1 && a1 + a2 == vi {
            if let Some(res) = solve_with_three_smallest(&v, n, (a0, a1, a2)) {
                return res;
            }
        }
    }
 
    unreachable!()
    //   let v0 = v[0];
    //   let v1 = v[1];
    //   let v2 = v[2];
    //   let a0 = (v0 + v1 - v2) / 2;
    //   let a1 = (v0 + v2 - v1) / 2;
    //   let a2 = (v1 + v2 - v0) / 2;
    //   if a0 + a1 == v0 && a0 + a2 == v1 && a1 + a2 == v2 {
    //       solve_with_three_smallest(v, n, (a0, a1, a2)).unwrap()
    //   } else {
    //       todo!()
    //   }
 
    // // Guess the three smallest elements
    // let v0 = v[0];
    // let v1 = v[1];
    // let v2 = v[2];
    // let a0 = (v0 + v1 - v2) / 2;
    // let a1 = (v0 + v2 - v1) / 2;
    // let a2 = (v1 + v2 - v0) / 2;
    // if a0 + a1 == v0 && a0 + a2 == v1 && a1 + a2 == v2 {
    //     solve_with_three_smallest(v, n, (a0, a1, a2)).unwrap()
    // } else {
    //     todo!()
    // }
}
 
fn main() {
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let mut lines = stdin.lines();
    let n: usize = lines.next().unwrap().unwrap().parse().unwrap();
    let v = lines
        .next()
        .unwrap()
        .unwrap()
        .split_whitespace()
        .map(|v| v.parse().unwrap())
        .collect();
 
    print_iter(solve(v, n).into_iter());
}
 
#[cfg(test)]
mod tests {
    use super::*;
 
    fn construct_input(v: &[usize]) -> Vec<usize> {
        let mut res = Vec::new();
        for i in 0..v.len() {
            for j in i + 1..v.len() {
                res.push(v[i] + v[j]);
            }
        }
        res
    }
 
    fn assert_similar(real: Vec<usize>, test: Vec<usize>) {
        let mut real = construct_input(&real);
        let mut test = construct_input(&test);
        real.sort();
        test.sort();
        assert_eq!(real, test);
    }
 
    fn assert_test(res: Vec<usize>) {
        let input = construct_input(&res);
        let n = res.len();
        assert_similar(res, solve(input, n));
    }
 
    #[test]
    fn test_sample() {
        assert_test(vec![1, 3, 3, 3]);
    }
 
    #[test]
    fn test_many() {
        assert_test(vec![1, 2, 3, 4]);
        assert_test(vec![1, 2, 3, 4, 5]);
        assert_test(vec![1, 10, 11, 12]);
        assert_test(vec![1, 11, 12, 13]);
        assert_test(vec![1, 10, 20, 30]);
    }
 
    #[test]
    fn test_medium() {
        
        assert_test(vec![1, 2, 3, 4,1, 2, 3, 4, 5,100,5,19,312,523,456,34,56,12,4,2]);
    }
 
    #[test]
    fn test_big() {
        use rand::distributions::{Distribution, Uniform};
        use std::time::{Duration, Instant};
 
        const ITERS: u32 = 30;
        const SIZE: usize = 100;
        let mut time = Duration::from_nanos(1);
        for i in 0..ITERS {
            let mut model: Vec<usize> = vec![0; SIZE];
 
            for i in 0..SIZE {
                model[i] = Uniform::from(0..1_000_000).sample(&mut rand::thread_rng());
            }
 
            let input = construct_input(&model);
 
            std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);
            let start = Instant::now();
            std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);
            let output = solve(input, model.len());
            std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);
            let stop = Instant::now();
            std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);
            time += stop - start;
 
            assert_similar(model, output);
        }
 
        let time = (time / ITERS).as_secs_f64();
        assert!(time < 1.0, "Took time {}", time);
    }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 2, 3

Verdict: ACCEPTED

Test 8

Group: 2, 3

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 2, 3

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED