QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#744982 | #9746. 平方根 | ggghe | WA | 3ms | 10868kb | Rust | 4.4kb | 2024-11-14 01:10:02 | 2024-11-14 01:10:07 |
Judging History
answer
use std::cmp::{max, min};
fn main() {
input! {
s: bytes
}
let mut c0 = 0;
let mut c1 = 0;
for &i in &s {
if i == b'1' {
c1 += 1;
} else {
c0 += 1;
}
}
let mut ans = 0.0;
// sq(x) = sq(x / 2) odd
// = sq(x / 2) + sq(x / 2 - 1) even
struct ENV {
cache: Vec<f64>,
}
let mut env = ENV {
cache: vec![-1.0; 1_000_010],
};
fn calc(x: i64, env: &mut ENV) -> f64 {
if x <= 0 {
return 0.0;
}
if x == 1 {
return 1.0;
}
if env.cache[at(x)] != -1.0 {
return env.cache[at(x)];
}
let mut res = f64::sqrt(x as f64);
if x % 2 == 0 {
let cur = calc(x / 2, env) + calc((x / 2) - 1, env);
if cur > res {
res = cur;
}
} else {
let cur = 2.0 * calc(x / 2, env);
if cur > res {
res = cur;
}
}
env.cache[at(x)] = res;
res
}
let n = s.len();
let mut i = 0;
while i < n {
if s[i] == b'0' {
i += 1;
continue;
}
let st = i;
while i < n && s[i] == b'1' {
i += 1;
}
let len = i - st;
ans += calc(len as i64, &mut env);
}
println!("{}", ans);
}
fn at(i: i64) -> usize {
i as usize
}
#[macro_export]
macro_rules! input {
() => {};
(mut $var:ident: $t:tt, $($rest:tt)*) => {
let mut $var = __input_inner!($t);
input!($($rest)*)
};
($var:ident: $t:tt, $($rest:tt)*) => {
let $var = __input_inner!($t);
input!($($rest)*)
};
(mut $var:ident: $t:tt) => {
let mut $var = __input_inner!($t);
};
($var:ident: $t:tt) => {
let $var = __input_inner!($t);
};
}
#[macro_export]
macro_rules! __input_inner {
(($($t:tt),*)) => {
($(__input_inner!($t)),*)
};
([$t:tt; $n:expr]) => {
(0..$n).map(|_| __input_inner!($t)).collect::<Vec<_>>()
};
([$t:tt]) => {{
let n = __input_inner!(usize);
(0..n).map(|_| __input_inner!($t)).collect::<Vec<_>>()
}};
(chars) => {
__input_inner!(String).chars().collect::<Vec<_>>()
};
(bytes) => {
__input_inner!(String).into_bytes()
};
(usize1) => {
__input_inner!(usize) - 1
};
($t:ty) => {
$crate::read::<$t>()
};
}
#[macro_export]
macro_rules! println {
($($arg:tt)*) => {
$crate::write(|w| {
use std::io::Write;
std::writeln!(w, $($arg)*).unwrap()
})
};
}
#[macro_export]
macro_rules! print {
($($arg:tt)*) => {
$crate::write(|w| {
use std::io::Write;
std::write!(w, $($arg)*).unwrap()
})
};
}
#[macro_export]
macro_rules! flush {
() => {
$crate::write(|w| {
use std::io::Write;
w.flush().unwrap()
})
};
}
pub fn read<T>() -> T
where
T: std::str::FromStr,
T::Err: std::fmt::Debug,
{
use std::cell::RefCell;
use std::io::*;
thread_local! {
static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
}
STDIN.with_borrow_mut(|r| {
let mut s = vec![];
loop {
let buf = r.fill_buf().unwrap();
if buf.is_empty() {
break;
}
if let Some(i) = buf.iter().position(u8::is_ascii_whitespace) {
s.extend_from_slice(&buf[..i]);
r.consume(i + 1);
if !s.is_empty() {
break;
}
} else {
s.extend_from_slice(buf);
let n = buf.len();
r.consume(n);
}
}
std::str::from_utf8(&s).unwrap().parse().unwrap()
})
}
pub fn write<F>(f: F)
where
F: FnOnce(&mut std::io::BufWriter<std::io::StdoutLock>),
{
use std::cell::RefCell;
use std::io::*;
thread_local! {
static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> =
RefCell::new(BufWriter::new(stdout().lock()));
}
STDOUT.with_borrow_mut(f)
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 9792kb
input:
1100110111
output:
4.82842712474619
result:
ok found '4.828427125', expected '4.828427125', error '0.000000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 9752kb
input:
0
output:
0
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 9828kb
input:
1
output:
1
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #4:
score: 0
Accepted
time: 3ms
memory: 10744kb
input:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
0
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 10868kb
input:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
495833.42379227304
result:
wrong answer 1st numbers differ - expected: '500000.4142136', found: '495833.4237923', error = '0.0083340'