#[doc = " https://github.com/hatoo/competitive-rust-snippets"] #[allow(unused_imports)] use std::cmp::{max, min, Ordering}; #[allow(unused_imports)] use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque}; #[allow(unused_imports)] use std::io::{stdin, stdout, BufWriter, Write}; #[allow(unused_imports)] use std::iter::FromIterator; mod util { use std::fmt::Debug; use std::io::{stdin, stdout, BufWriter, StdoutLock}; use std::str::FromStr; #[allow(dead_code)] pub fn line() -> String { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); line.trim().to_string() } #[allow(dead_code)] pub fn chars() -> Vec { line().chars().collect() } #[allow(dead_code)] pub fn gets() -> Vec where ::Err: Debug, { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); line.split_whitespace() .map(|t| t.parse().unwrap()) .collect() } #[allow(dead_code)] pub fn with_bufwriter) -> ()>(f: F) { let out = stdout(); let writer = BufWriter::new(out.lock()); f(writer) } } #[allow(unused_macros)] macro_rules ! get { ( $ t : ty ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; line . trim ( ) . parse ::<$ t > ( ) . unwrap ( ) } } ; ( $ ( $ t : ty ) ,* ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; let mut iter = line . split_whitespace ( ) ; ( $ ( iter . next ( ) . unwrap ( ) . parse ::<$ t > ( ) . unwrap ( ) , ) * ) } } ; ( $ t : ty ; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ ( $ t : ty ) ,*; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( $ ( $ t ) ,* ) ) . collect ::< Vec < _ >> ( ) } ; ( $ t : ty ;; ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; line . split_whitespace ( ) . map ( | t | t . parse ::<$ t > ( ) . unwrap ( ) ) . collect ::< Vec < _ >> ( ) } } ; ( $ t : ty ;; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( $ t ;; ) ) . collect ::< Vec < _ >> ( ) } ; } #[allow(unused_macros)] macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) ; } } const BIG_STACK_SIZE: bool = true; #[allow(dead_code)] fn main() { use std::thread; if BIG_STACK_SIZE { thread::Builder::new() .stack_size(32 * 1024 * 1024) .name("solve".into()) .spawn(solve) .unwrap() .join() .unwrap(); } else { solve(); } } const TRUE: &'static bool = &true; const FALSE: &'static bool = &false; #[derive(Clone, Debug)] #[doc = " Efficient bool collection"] pub struct BitSet { buf: Vec, size: usize, } impl BitSet { #[allow(dead_code)] pub fn new(size: usize) -> BitSet { BitSet { buf: vec![0; (size + 63) / 64], size: size, } } #[allow(dead_code)] pub fn set(&mut self, i: usize, b: bool) { assert!(i < self.size); if b { self.buf[i >> 6] |= 1 << (i & 63); } else { self.buf[i >> 6] &= !(1 << (i & 63)); } } #[allow(dead_code)] pub fn count_ones(&self) -> u32 { self.buf.iter().map(|x| x.count_ones()).sum() } #[allow(dead_code)] fn chomp(&mut self) { let r = self.size & 63; if r != 0 { if let Some(x) = self.buf.last_mut() { let d = 64 - r; *x = (*x << d) >> d; } } } } impl std::ops::Index for BitSet { type Output = bool; fn index(&self, index: usize) -> &bool { [FALSE, TRUE][(self.buf[index >> 6] >> (index & 63)) as usize & 1] } } impl std::ops::ShlAssign for BitSet { fn shl_assign(&mut self, x: usize) { let q = x >> 6; let r = x & 63; if q >= self.buf.len() { for x in &mut self.buf { *x = 0; } return; } if r == 0 { for i in (q..self.buf.len()).rev() { self.buf[i] = self.buf[i - q]; } } else { for i in (q + 1..self.buf.len()).rev() { self.buf[i] = (self.buf[i - q] << r) | (self.buf[i - q - 1] >> (64 - r)); } self.buf[q] = self.buf[0] << r; } for i in 0..q { self.buf[i] = 0; } self.chomp(); } } impl std::ops::Shl for BitSet { type Output = Self; fn shl(mut self, x: usize) -> Self { self <<= x; self } } impl std::ops::ShrAssign for BitSet { fn shr_assign(&mut self, x: usize) { let q = x >> 6; let r = x & 63; if q >= self.buf.len() { for x in &mut self.buf { *x = 0; } return; } if r == 0 { for i in 0..self.buf.len() - q { self.buf[i] = self.buf[i + q]; } } else { for i in 0..self.buf.len() - q - 1 { self.buf[i] = (self.buf[i + q] >> r) | (self.buf[i + q + 1] << (64 - r)); } let len = self.buf.len(); self.buf[len - q - 1] = self.buf[len - 1] >> r; } for i in self.buf.len() - q..self.buf.len() { self.buf[i] = 0; } } } impl std::ops::Shr for BitSet { type Output = Self; fn shr(mut self, x: usize) -> Self { self >>= x; self } } impl<'a> std::ops::BitAndAssign<&'a BitSet> for BitSet { fn bitand_assign(&mut self, rhs: &'a Self) { for (a, b) in self.buf.iter_mut().zip(rhs.buf.iter()) { *a &= *b; } } } impl<'a> std::ops::BitAnd<&'a BitSet> for BitSet { type Output = Self; fn bitand(mut self, rhs: &'a Self) -> Self { self &= rhs; self } } impl<'a> std::ops::BitOrAssign<&'a BitSet> for BitSet { fn bitor_assign(&mut self, rhs: &'a Self) { for (a, b) in self.buf.iter_mut().zip(rhs.buf.iter()) { *a |= *b; } self.chomp(); } } impl<'a> std::ops::BitOr<&'a BitSet> for BitSet { type Output = Self; fn bitor(mut self, rhs: &'a Self) -> Self { self |= rhs; self } } impl<'a> std::ops::BitXorAssign<&'a BitSet> for BitSet { fn bitxor_assign(&mut self, rhs: &'a Self) { for (a, b) in self.buf.iter_mut().zip(rhs.buf.iter()) { *a ^= *b; } self.chomp(); } } impl<'a> std::ops::BitXor<&'a BitSet> for BitSet { type Output = Self; fn bitxor(mut self, rhs: &'a Self) -> Self { self ^= rhs; self } } fn solve() { let n = get!(usize); let ws = get!(usize;;); let sum = ws.iter().sum::(); if sum % 2 == 1 { println!("impossible"); return; } let mut bitset = BitSet::new(10001); bitset.set(0, true); for w in ws { bitset |= &(bitset.clone() << w); } if bitset[sum / 2] { println!("possible"); } else { println!("impossible"); } }