Submission #2639636
Source Code Expand
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::io::*;
use std::ops::*;
use std::*;
// -----------------------------------------------
// Framework
// -----------------------------------------------
#[allow(unused)]
fn rl() -> String {
let mut buf = String::new();
io::stdin().read_line(&mut buf).unwrap();
buf.trim_right().to_owned()
}
#[allow(unused)]
fn rw<T>() -> Vec<T>
where
T: std::str::FromStr,
T::Err: std::fmt::Debug,
{
let mut buf = String::new();
io::stdin().read_line(&mut buf).unwrap();
buf.split_whitespace()
.map(|word| T::from_str(word).unwrap())
.collect()
}
trait IteratorExt: Iterator + Sized {
fn vec(self) -> Vec<Self::Item> {
self.collect()
}
}
impl<T: Iterator> IteratorExt for T {}
#[allow(unused)]
macro_rules! debug {
($($arg:expr),*) => {
#[cfg(debug_assertions)]
{
let entries = &[
$((
&stringify!($arg).to_string() as &fmt::Debug,
&($arg) as &fmt::Debug,
)),*
];
eprintln!("{:?}", DebugMap(entries));
}
};
}
#[allow(unused)]
struct DebugMap<'a>(&'a [(&'a fmt::Debug, &'a fmt::Debug)]);
impl<'a> std::fmt::Debug for DebugMap<'a> {
fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
let mut m = fmt.debug_map();
for &(key, value) in self.0.iter() {
m.entry(key, value);
}
m.finish()
}
}
// -----------------------------------------------
// Polyfill
// -----------------------------------------------
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct Rev<T>(pub T);
impl<T: PartialOrd> PartialOrd for Rev<T> {
fn partial_cmp(&self, other: &Rev<T>) -> Option<Ordering> {
other.0.partial_cmp(&self.0)
}
}
impl<T: Ord> Ord for Rev<T> {
fn cmp(&self, other: &Rev<T>) -> Ordering {
other.0.cmp(&self.0)
}
}
#[allow(unused)]
macro_rules! eprintln {
($($arg:expr),*) => { _eprintln(format_args!($($arg),*)) }
}
fn _eprintln(args: fmt::Arguments) {
let err = std::io::stderr();
let mut err = err.lock();
err.write_fmt(args).unwrap();
err.write(b"\n").unwrap();
}
// -----------------------------------------------
// Solution
// -----------------------------------------------
fn find(N: i32, m: i32, collect: bool) -> Option<Vec<i32>> {
let mut set = Vec::new();
let mut s = N;
let mut x = m;
while x >= 1 {
if s >= x {
s -= x;
if collect {
set.push(x);
}
if s == 0 {
return Some(set);
}
}
x -= 1;
}
None
}
pub fn main() {
let N = rl().parse::<i32>().unwrap();
let mut l = 0; // ng
let mut r = N; // ok
while r - l > 1 {
let m = l + (r - l) / 2;
let ok = find(N, m, false).is_some();
if ok {
r = m;
} else {
l = m;
}
}
let set = find(N, r, true).unwrap();
for x in set.into_iter().rev() {
println!("{}", x);
}
return;
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_ok() {
assert_eq!(7, 1 + 2 * 3);
}
}
Submission Info
Submission Time |
|
Task |
B - Exactly N points |
User |
vain0 |
Language |
Rust (1.15.1) |
Score |
300 |
Code Size |
3482 Byte |
Status |
AC |
Exec Time |
16 ms |
Memory |
4352 KB |
Judge Result
Set Name |
sample |
dataset1 |
dataset2 |
Score / Max Score |
0 / 0 |
200 / 200 |
100 / 100 |
Status |
|
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt, sample-03.txt |
dataset1 |
sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt |
dataset2 |
sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, sample-01.txt, sample-02.txt, sample-03.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
2 ms |
4352 KB |
01-02.txt |
AC |
2 ms |
4352 KB |
01-03.txt |
AC |
2 ms |
4352 KB |
01-04.txt |
AC |
2 ms |
4352 KB |
01-05.txt |
AC |
2 ms |
4352 KB |
01-06.txt |
AC |
2 ms |
4352 KB |
01-07.txt |
AC |
2 ms |
4352 KB |
01-08.txt |
AC |
2 ms |
4352 KB |
01-09.txt |
AC |
2 ms |
4352 KB |
01-10.txt |
AC |
2 ms |
4352 KB |
02-01.txt |
AC |
16 ms |
4352 KB |
02-02.txt |
AC |
16 ms |
4352 KB |
02-03.txt |
AC |
16 ms |
4352 KB |
02-04.txt |
AC |
15 ms |
4352 KB |
02-05.txt |
AC |
16 ms |
4352 KB |
02-06.txt |
AC |
8 ms |
4352 KB |
02-07.txt |
AC |
5 ms |
4352 KB |
02-08.txt |
AC |
15 ms |
4352 KB |
sample-01.txt |
AC |
2 ms |
4352 KB |
sample-02.txt |
AC |
2 ms |
4352 KB |
sample-03.txt |
AC |
2 ms |
4352 KB |