Submission #8431533
Source Code Expand
// SNIPPET num
pub trait PrimitiveInteger:
Sized + Ord +
std::ops::Add<Output=Self> +
std::ops::Sub<Output=Self> +
std::ops::Div<Output=Self>
{
fn one() -> Self;
fn abs_diff(self, rhs: Self) -> Self;
fn rem_euclid(self, rhs: Self) -> Self;
}
macro_rules! impl_primitive_integer {
( $($t: ty)* ) => { $(
impl PrimitiveInteger for $t {
fn one() -> $t {
1
}
fn abs_diff(self, rhs: $t) -> $t {
if self < rhs { rhs - self } else { self - rhs }
}
#[allow(unused_comparisons)]
fn rem_euclid(self, rhs: $t) -> $t {
let r = self % rhs;
if r < 0 {
if rhs < 0 { r - rhs } else { r + rhs }
} else {
r
}
}
}
)* }
}
impl_primitive_integer!(u8 u16 u32 u64 usize i8 i16 i32 i64 isize);
pub trait PrimitiveUnsigned: PrimitiveInteger {
fn ceil_div(self, rhs: Self) -> Self;
fn round_div(self, rhs: Self) -> Self;
fn log2(self) -> Option<Self>;
fn ceil_log2(self) -> Option<Self>;
fn sqrt(self) -> Self;
}
macro_rules! impl_primitive_unsigned {
( $($t: ty)* ) => { $(
impl PrimitiveUnsigned for $t {
fn ceil_div(self, rhs: $t) -> $t {
(self + rhs - 1) / rhs
}
fn round_div(self, rhs: $t) -> $t {
(self + rhs/2) / rhs
}
fn log2(mut self) -> Option<$t> {
if self == 0 {
None
} else {
let mut ans = 0;
while self > 1 {
ans += 1;
self /= 2;
}
Some(ans)
}
}
fn ceil_log2(self) -> Option<$t> {
self.log2().map(|x| {
(self + ((1<<x) - 1)).log2().unwrap()
})
}
fn sqrt(self) -> $t {
(self as f64).sqrt() as $t
}
}
)* }
}
impl_primitive_unsigned!(u8 u16 u32 u64 usize);
pub fn gcd(a: u64, b: u64) -> u64 {
if b == 0 { a } else { gcd(b, a%b) }
}
pub fn bezout(a: i64, b: i64) -> (i64, i64, u64) {
let (x, y, g) = bezout_sub((a * a.signum()) as u64, (b * b.signum()) as u64);
(x * a.signum(), y * b.signum(), g)
}
fn bezout_sub(a: u64, b: u64) -> (i64, i64, u64) {
if b == 0 { (1, 0, a) } else {
let m = (a / b) as i64;
let (x, y, g) = bezout_sub(b, a%b);
(y, x - m*y, g)
}
}
macro_rules! forward_ref_unop {
(impl $op:ident, $method:ident for $t:ty) => {
impl std::ops::$op for &$t {
type Output = <$t as std::ops::$op>::Output;
fn $method(self) -> <$t as std::ops::$op>::Output {
std::ops::$op::$method(*self)
}
}
}
}
macro_rules! forward_ref_binop {
(impl $op:ident, $method:ident for $t:ty, $u:ty) => {
impl<'a> std::ops::$op<$u> for &'a $t {
type Output = <$t as std::ops::$op<$u>>::Output;
fn $method(self, other: $u) -> <$t as std::ops::$op<$u>>::Output {
std::ops::$op::$method(*self, other)
}
}
impl std::ops::$op<&$u> for $t {
type Output = <$t as std::ops::$op<$u>>::Output;
fn $method(self, other: &$u) -> <$t as std::ops::$op<$u>>::Output {
std::ops::$op::$method(self, *other)
}
}
impl std::ops::$op<&$u> for &$t {
type Output = <$t as std::ops::$op<$u>>::Output;
fn $method(self, other: &$u) -> <$t as std::ops::$op<$u>>::Output {
std::ops::$op::$method(*self, *other)
}
}
}
}
macro_rules! forward_ref_op_assign {
(impl $op:ident, $method:ident for $t:ty, $u:ty) => {
impl std::ops::$op<&$u> for $t {
fn $method(&mut self, other: &$u) {
std::ops::$op::$method(self, *other);
}
}
}
}
// SNIPPET bsearch
pub trait BSearch: Sized {
type Item;
fn is_empty(&self) -> bool;
fn leftmost_item(&self) -> Self::Item;
fn rightmost_item(&self) -> Self::Item;
fn middle_item(&self) -> Self::Item;
fn left_half(&self) -> Self;
fn right_half(&self) -> Self;
fn is_bsearch_converged(&self) -> bool;
fn bsearch_left_max<F>(&self, mut is_left: F) -> Option<Self::Item>
where
F: FnMut(&Self::Item) -> bool
{
if self.is_empty() {
None
} else if !is_left(&self.leftmost_item()) {
None
} else {
let rightmost = self.rightmost_item();
if is_left(&rightmost) {
Some(rightmost)
} else {
Some(bsearch_left_max_sub(self, is_left))
}
}
}
fn bsearch_right_min<F>(&self, mut is_right: F) -> Option<Self::Item>
where
F: FnMut(&Self::Item) -> bool
{
if self.is_empty() {
None
} else if !is_right(&self.rightmost_item()) {
None
} else {
let leftmost = self.leftmost_item();
if is_right(&leftmost) {
Some(leftmost)
} else {
Some(bsearch_right_min_sub(self, is_right))
}
}
}
}
fn bsearch_left_max_sub<Items, T, F>(items: &Items, mut is_left: F) -> T
where
Items: BSearch<Item=T>,
F: FnMut(&T) -> bool
{
if items.is_bsearch_converged() {
items.leftmost_item()
} else {
if is_left(&items.middle_item()) {
bsearch_left_max_sub(&items.right_half(), is_left)
} else {
bsearch_left_max_sub(&items.left_half(), is_left)
}
}
}
fn bsearch_right_min_sub<Items, T, F>(items: &Items, mut is_right: F) -> T
where
Items: BSearch<Item=T>,
F: FnMut(&T) -> bool
{
if items.is_bsearch_converged() {
items.rightmost_item()
} else {
if is_right(&items.middle_item()) {
bsearch_right_min_sub(&items.left_half(), is_right)
} else {
bsearch_right_min_sub(&items.right_half(), is_right)
}
}
}
impl<T: PrimitiveInteger + Clone> BSearch for std::ops::Range<T> {
type Item = T;
fn is_empty(&self) -> bool {
self.end <= self.start
}
fn leftmost_item(&self) -> T {
self.start.clone()
}
fn rightmost_item(&self) -> T {
self.end.clone() - T::one()
}
fn middle_item(&self) -> T {
(self.start.clone() + self.end.clone()) / (T::one() + T::one())
}
fn left_half(&self) -> std::ops::Range<T> {
self.start.clone()..(self.middle_item() + T::one())
}
fn right_half(&self) -> std::ops::Range<T> {
self.middle_item()..self.end.clone()
}
fn is_bsearch_converged(&self) -> bool {
BSearch::is_empty(self) || self.end.clone() - self.start.clone() <= T::one() + T::one()
}
}
impl<'a, T> BSearch for &'a [T] {
type Item = &'a T;
fn is_empty(&self) -> bool {
<[T]>::is_empty(self)
}
fn leftmost_item(&self) -> &'a T {
self.first().unwrap()
}
fn rightmost_item(&self) -> &'a T {
self.last().unwrap()
}
fn middle_item(&self) -> &'a T {
self.get(self.len() / 2).unwrap()
}
fn left_half(&self) -> &'a [T] {
&self[..(self.len() / 2 + 1)]
}
fn right_half(&self) -> &'a [T] {
&self[(self.len() / 2)..]
}
fn is_bsearch_converged(&self) -> bool {
self.len() <= 2
}
}
pub trait SliceBSearch {
type Item;
fn bsearch_left_max<F>(&self, is_left: F) -> Option<&Self::Item>
where
F: FnMut(&Self::Item) -> bool;
fn bsearch_index_left_max<F>(&self, is_left: F) -> Option<usize>
where
F: FnMut(&Self::Item) -> bool;
fn bsearch_right_min<F>(&self, is_right: F) -> Option<&Self::Item>
where
F: FnMut(&Self::Item) -> bool;
fn bsearch_index_right_min<F>(&self, is_right: F) -> Option<usize>
where
F: FnMut(&Self::Item) -> bool;
}
impl<T> SliceBSearch for [T] {
type Item = T;
fn bsearch_left_max<F>(&self, mut is_left: F) -> Option<&T>
where
F: FnMut(&T) -> bool
{
BSearch::bsearch_left_max(&self, |&x| is_left(x))
}
fn bsearch_index_left_max<F>(&self, mut is_left: F) -> Option<usize>
where
F: FnMut(&T) -> bool
{
(0..self.len()).bsearch_left_max(|&i| {
let x = unsafe { self.get_unchecked(i) };
is_left(x)
})
}
fn bsearch_right_min<F>(&self, mut is_right: F) -> Option<&T>
where
F: FnMut(&T) -> bool
{
BSearch::bsearch_right_min(&self, |&x| is_right(x))
}
fn bsearch_index_right_min<F>(&self, mut is_right: F) -> Option<usize>
where
F: FnMut(&T) -> bool
{
(0..self.len()).bsearch_right_min(|&i| {
let x = unsafe { self.get_unchecked(i) };
is_right(x)
})
}
}
// SNIPPET read
pub trait Readable {
type Output;
fn words_count() -> usize;
fn read_words(words: &[&str]) -> Result<Self::Output, String>;
}
#[macro_export]
macro_rules! readable {
( $t:ty, $words_count:expr, |$words:ident| $read_words:expr ) => {
impl Readable for $t {
type Output = $t;
fn words_count() -> usize { $words_count }
fn read_words($words: &[&str]) -> Result<$t, String> {
Ok($read_words)
}
}
};
}
readable!((), 1, |_ss| ());
readable!(String, 1, |ss| ss[0].to_string());
impl Readable for char {
type Output = char;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<char, String> {
let chars: Vec<char> = words[0].chars().collect();
if chars.len() == 1 {
Ok(chars[0])
} else {
Err(format!("cannot parse `{}` as a char", words[0]))
}
}
}
pub struct Chars();
impl Readable for Chars {
type Output = Vec<char>;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<Vec<char>, String> {
Ok(words[0].chars().collect())
}
}
macro_rules! impl_readable_for_ints {
( $( $t:ty )* ) => { $(
impl Readable for $t {
type Output = Self;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<$t, String> {
use std::str::FromStr;
<$t>::from_str(words[0]).map_err(|_| {
format!("cannot parse `{}` as {}", words[0], stringify!($t))
})
}
}
)* };
}
impl_readable_for_ints!(i8 u8 i16 u16 i32 u32 i64 u64 isize usize f32 f64);
macro_rules! define_one_origin_int_types {
( $new_t:ident $int_t:ty ) => {
#[allow(non_camel_case_types)]
pub struct $new_t;
impl Readable for $new_t {
type Output = $int_t;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<Self::Output, String> {
<$int_t>::read_words(words).map(|n| n-1)
}
}
};
( $new_t:ident $int_t:ty; $( $inner_new_t:ident $inner_int_t:ty );* ) => {
define_one_origin_int_types!($new_t $int_t);
define_one_origin_int_types!($($inner_new_t $inner_int_t);*);
};
}
define_one_origin_int_types!(u8_ u8; u16_ u16; u32_ u32; u64_ u64; usize_ usize);
macro_rules! impl_readable_for_tuples {
( $t:ident $var:ident ) => ();
( $t:ident $var:ident; $( $inner_t:ident $inner_var:ident );* ) => {
impl_readable_for_tuples!($($inner_t $inner_var);*);
impl<$t: Readable, $($inner_t: Readable),*> Readable
for ($t, $($inner_t),*)
{
type Output = ( <$t>::Output, $(<$inner_t>::Output),* );
fn words_count() -> usize {
let mut n = <$t>::words_count();
$(
n += <$inner_t>::words_count();
)*
n
}
#[allow(unused_assignments)]
fn read_words(words: &[&str]) ->
Result<Self::Output, String>
{
let mut start = 0;
let $var = <$t>::read_words(
&words[start .. start+<$t>::words_count()]
)?;
start += <$t>::words_count();
$(
let $inner_var =
<$inner_t>::read_words(
&words[start .. start+<$inner_t>::words_count()]
)?;
start += <$inner_t>::words_count();
)*
Ok(( $var, $($inner_var),* ))
}
}
};
}
impl_readable_for_tuples!(T8 x8; T7 x7; T6 x6; T5 x5; T4 x4; T3 x3; T2 x2; T1 x1);
pub trait ReadableFromLine {
type Output;
fn read_line(line: &str) -> Result<Self::Output, String>;
}
fn split_into_words(line: &str) -> Vec<&str> {
#[allow(deprecated)]
line.trim_right_matches('\n').split_whitespace().collect()
}
impl<T: Readable> ReadableFromLine for T {
type Output = T::Output;
fn read_line(line: &str) -> Result<T::Output, String> {
let words = split_into_words(line);
if words.len() != T::words_count() {
return Err(format!("line `{}` has {} words, expected {}",
line, words.len(), T::words_count()));
}
T::read_words(&words)
}
}
macro_rules! impl_readable_from_line_for_tuples_with_from_iterator {
( $u:ident : $( + $bound:path )* => $seq_in:ty, $seq_out:ty; $t:ident $var:ident ) => {
impl<$u: Readable> ReadableFromLine for $seq_in
where
<$u as Readable>::Output: Sized $(+ $bound)*
{
type Output = $seq_out;
fn read_line(line: &str) -> Result<$seq_out, String> {
let n = $u::words_count();
let words = split_into_words(line);
if words.len() % n != 0 {
return Err(format!("line `{}` has {} words, expected multiple of {}",
line, words.len(), n));
}
let mut result = Vec::new();
for chunk in words.chunks(n) {
match $u::read_words(chunk) {
Ok(v) => result.push(v),
Err(msg) => {
let flagment_msg = if n == 1 {
format!("word {}", result.len())
} else {
let l = result.len();
format!("words {}-{}", n*l + 1, (n+1) * l)
};
return Err(format!(
"{} of line `{}`: {}", flagment_msg, line, msg
));
}
}
}
Ok(result.into_iter().collect())
}
}
impl<T: Readable, $u: Readable> ReadableFromLine for (T, $seq_in)
where
<$u as Readable>::Output: Sized $(+ $bound)*
{
type Output = (T::Output, $seq_out);
fn read_line(line: &str) -> Result<Self::Output, String> {
let n = T::words_count();
#[allow(deprecated)]
let trimmed = line.trim_right_matches('\n');
let words_and_rest: Vec<&str> = trimmed.splitn(n + 1, ' ').collect();
if words_and_rest.len() < n {
return Err(format!("line `{}` has {} words, expected at least {}",
line, words_and_rest.len(), n));
}
let words = &words_and_rest[..n];
let empty_str = "";
let rest = words_and_rest.get(n).unwrap_or(&empty_str);
Ok((T::read_words(words)?, <$seq_in>::read_line(rest)?))
}
}
};
( $u:ident : $( + $bound:path )* => $seq_in:ty, $seq_out:ty;
$t:ident $var:ident, $( $inner_t:ident $inner_var:ident ),+ ) => {
impl_readable_from_line_for_tuples_with_from_iterator!(
$u: $(+ $bound)* => $seq_in, $seq_out; $($inner_t $inner_var),+
);
impl<$t: Readable, $($inner_t: Readable),+ , $u: Readable> ReadableFromLine
for ($t, $($inner_t),+ , $seq_in)
where
<$u as Readable>::Output: Sized $(+ $bound)*
{
type Output = ($t::Output, $($inner_t::Output),+ , $seq_out);
fn read_line(line: &str) -> Result<Self::Output, String> {
let mut n = $t::words_count();
$(
n += $inner_t::words_count();
)+
#[allow(deprecated)]
let trimmed = line.trim_right_matches('\n');
let words_and_rest: Vec<&str> = trimmed.splitn(n + 1, ' ')
.collect();
if words_and_rest.len() < n {
return Err(
format!("line `{}` has {} words, expected at least {}",
line, words_and_rest.len(), n)
);
}
let words = &words_and_rest[..n];
let empty_str = "";
let rest = words_and_rest.get(n).unwrap_or(&empty_str);
let ($var, $($inner_var),*) =
<($t, $($inner_t),+)>::read_words(words)?;
Ok(($var, $($inner_var),* , <$seq_in>::read_line(rest)?))
}
}
};
}
#[macro_export]
macro_rules! readable_collection {
($u:ident => $collection_in:ty, $collection_out:ty) => {
impl_readable_from_line_for_tuples_with_from_iterator!(
$u: => $collection_in, $collection_out;
T8 x8, T7 x7, T6 x6, T5 x5, T4 x4, T3 x3, T2 x2, T1 x1
);
};
($u:ident : $( $bound:path ),* => $collection_in:ty, $collection_out:ty) => {
impl_readable_from_line_for_tuples_with_from_iterator!(
$u: $(+ $bound)* => $collection_in, $collection_out;
T8 x8, T7 x7, T6 x6, T5 x5, T4 x4, T3 x3, T2 x2, T1 x1
);
}
}
readable_collection!(U => Vec<U>, Vec<U::Output>);
readable_collection!(
U => std::collections::VecDeque<U>, std::collections::VecDeque<U::Output>
);
readable_collection!(
U: Eq, std::hash::Hash => std::collections::HashSet<U>, std::collections::HashSet<U::Output>
);
readable_collection!(
U: Ord => std::collections::BTreeSet<U>, std::collections::BTreeSet<U::Output>
);
readable_collection!(
U: Ord => std::collections::BinaryHeap<U>, std::collections::BinaryHeap<U::Output>
);
pub fn read<T: ReadableFromLine>() -> T::Output {
let mut line = String::new();
std::io::stdin().read_line(&mut line).unwrap();
T::read_line(&line).unwrap()
}
#[macro_export]
macro_rules! read {
() => {
let mut line = String::new();
std::io::stdin().read_line(&mut line).unwrap();
};
( $pat:pat = $t:ty ) => {
let $pat = read::<$t>();
};
( $( $pat:pat = $t:ty ),+ ) => {
read!(($($pat),*) = ($($t),*));
};
}
#[macro_export]
macro_rules! readls {
( $( $pat:pat = $t:ty ),+ ) => {
$(
read!($pat = $t);
)*
};
}
pub fn readx<T: ReadableFromLine>() -> Vec<T::Output> {
use std::io::{self, BufRead};
let stdin = io::stdin();
let result = stdin.lock().lines().map(|line_result| {
let line = line_result.expect("read from stdin failed");
T::read_line(&line).unwrap()
}).collect();
result
}
#[macro_export]
macro_rules! readx_loop {
( |$pat:pat = $t:ty| $body:expr ) => {
{
use std::io::BufRead;
let stdin = std::io::stdin();
for line in stdin.lock().lines() {
let line = line.expect("read from stdin failed");
let $pat = <$t>::read_line(&line).unwrap();
$body
}
}
};
( |$($pat:pat = $t:ty),*| $body:expr ) => {
readx_loop!(|($($pat),*) = ($($t),*)| $body);
};
}
pub fn readn<T: ReadableFromLine>(n: usize) -> Vec<T::Output> {
use std::io::{self, BufRead};
let stdin = io::stdin();
let result: Vec<T::Output> = stdin.lock().lines().take(n).map(|line_result| {
let line = line_result.expect("read from stdin failed");
T::read_line(&line).unwrap()
}).collect();
if result.len() < n {
panic!("expected reading {} lines, but only {} lines are read",
n, result.len());
}
result
}
#[macro_export]
macro_rules! readn_loop {
( $n:expr, |$pat:pat = $t:ty| $body:expr ) => {
{
use std::io::BufRead;
let stdin = std::io::stdin();
let mut lock = stdin.lock();
for _ in 0..$n {
let mut line = String::new();
lock.read_line(&mut line).expect("read from stdin failed");
let $pat = <$t>::read_line(&line).unwrap();
$body
}
}
};
( $n:expr, |$($pat:pat = $t:ty),*| $body:expr ) => {
readn_loop!($n, |($($pat),*) = ($($t),*)| $body);
};
}
pub trait Words {
fn read<T: Readable>(&self) -> T::Output;
}
impl<'a> Words for [&'a str] {
fn read<T: Readable>(&self) -> T::Output {
T::read_words(self).unwrap()
}
}
impl<'a> Words for &'a str {
fn read<T: Readable>(&self) -> T::Output {
T::read_words(&[self]).unwrap()
}
}
// (sport, number of people)
fn max_sport(table: &[Vec<usize>], inclusion: &[bool]) -> (usize, usize) {
let mut nums = vec![0; table[0].len()];
for row in table {
let i = row.iter().cloned().find(|&s| inclusion[s]).unwrap();
nums[i] += 1;
}
nums.iter().cloned().enumerate().max_by_key(|&(_, n)| n).unwrap()
}
fn main() {
read!(participant_count = usize, sport_count = usize);
let table = readx::<Vec<usize_>>();
let ans = (1..participant_count+1).bsearch_right_min(|&k| {
let mut inclusion = vec![true; sport_count];
for _ in 0..sport_count {
let (s, count) = max_sport(&table, &inclusion);
if count <= k {
return true;
}
inclusion[s] = false;
}
false
}).unwrap();
println!("{}", ans);
}
Submission Info
Submission Time |
|
Task |
B - Sports Festival |
User |
avtomat |
Language |
Rust (1.15.1) |
Score |
700 |
Code Size |
22488 Byte |
Status |
AC |
Exec Time |
138 ms |
Memory |
4476 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
700 / 700 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
2 ms |
4352 KB |
sample_02.txt |
AC |
2 ms |
4352 KB |
sample_03.txt |
AC |
2 ms |
4352 KB |
subtask_1_01.txt |
AC |
2 ms |
4352 KB |
subtask_1_02.txt |
AC |
2 ms |
4352 KB |
subtask_1_03.txt |
AC |
2 ms |
4352 KB |
subtask_1_04.txt |
AC |
2 ms |
4352 KB |
subtask_1_05.txt |
AC |
2 ms |
4352 KB |
subtask_1_06.txt |
AC |
4 ms |
4352 KB |
subtask_1_07.txt |
AC |
12 ms |
4476 KB |
subtask_1_08.txt |
AC |
3 ms |
4352 KB |
subtask_1_09.txt |
AC |
2 ms |
4352 KB |
subtask_1_10.txt |
AC |
2 ms |
4352 KB |
subtask_1_11.txt |
AC |
9 ms |
4352 KB |
subtask_1_12.txt |
AC |
2 ms |
4352 KB |
subtask_1_13.txt |
AC |
3 ms |
4352 KB |
subtask_1_14.txt |
AC |
9 ms |
4352 KB |
subtask_1_15.txt |
AC |
84 ms |
4352 KB |
subtask_1_16.txt |
AC |
12 ms |
4352 KB |
subtask_1_17.txt |
AC |
18 ms |
4352 KB |
subtask_1_18.txt |
AC |
138 ms |
4352 KB |