QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#578396 | #9307. Clock Master | shift | AC ✓ | 245ms | 5004kb | C++20 | 5.6kb | 2024-09-20 18:52:20 | 2024-09-20 18:52:20 |
Judging History
answer
// #pragma once
// C
#include <cassert>
#include <cctype>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <csetjmp>
#include <cstdarg>
#include <cstddef>
#include <cstdlib>
#include <cstdint>
// C++
#include <bitset>
#include <complex>
#include <algorithm>
#include <bitset>
#include <functional>
#include <iterator>
#include <limits>
#include <memory>
#include <new>
#include <numeric>
#include <typeinfo>
#include <utility>
#include <array>
#include <atomic>
#include <initializer_list>
#include <ratio>
#include <scoped_allocator>
#include <tuple>
#include <typeindex>
#include <type_traits>
#if _HAS_CXX17
#include <any>
// #include <execution>
#include <optional>
#include <variant>
#include <string_view>
#endif
#if _HAS_CXX20
#include <bit>
#include <compare>
#include <concepts>
#include <numbers>
#include <ranges>
#include <span>
#include <source_location>
#include <version>
#endif
#if _HAS_CXX23
#include <expected>
#include <stdatomic.h>
#if __cpp_impl_coroutine
#include <coroutine>
#endif
#endif
// C
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
// #include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cuchar>
// C++
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <shared_mutex>
#if _HAS_CXX17
#include <any>
#include <charconv>
// #include <execution>
#include <filesystem>
#include <optional>
#include <memory_resource>
#include <variant>
#endif
#if _HAS_CXX20
#include <barrier>
#include <bit>
#include <compare>
#include <concepts>
#include <format>
#include <latch>
#include <numbers>
#include <ranges>
#include <span>
#include <stop_token>
#include <semaphore>
#include <source_location>
#include <syncstream>
#include <version>
#endif
#if _HAS_CXX23
#include <expected>
#include <spanstream>
#if __has_include(<stacktrace>)
#include <stacktrace>
#endif
#include <stdatomic.h>
#include <stdfloat>
#endif
using i64 = long long;
using u64 = unsigned long long;
// https://github.com/Heltion/debug.h/blob/main/debug.h
template <class T, size_t size = std::tuple_size<T>::value> std::string to_debug(T, std::string s = "") requires(not std::ranges::range<T>);
std::string to_debug(auto x) requires requires(std::ostream& os) { os << x; } { return static_cast<std::ostringstream>(std::ostringstream() << x).str(); }
std::string to_debug(std::ranges::range auto x, std::string s = "") requires(not std::is_same_v<decltype(x), std::string>) {
for (auto xi : x) { s += ", " + to_debug(xi); }
return "[" + s.substr(s.empty() ? 0 : 2) + "]";
}
template <class T, size_t size> std::string to_debug(T x, std::string s) requires(not std::ranges::range<T>) {
[&]<size_t... I>(std::index_sequence<I...>) { ((s += ", " + to_debug(get<I>(x))), ...); }(std::make_index_sequence<size>());
return "(" + s.substr(s.empty() ? 0 : 2) + ")";
}
#define debug(...) std::cerr << __FILE__ ":" << __LINE__ << ": (" #__VA_ARGS__ ") = " << to_debug(std::tuple(__VA_ARGS__)) << "\n"
std::vector<int> minp, primes;
void sieve(int n) {
minp.assign(n + 1, 0);
primes.clear();
for (int i = 2; i <= n; i++) {
if (minp[i] == 0) {
minp[i] = i;
primes.push_back(i);
}
for (auto p : primes) {
if (i * p > n) {
break;
}
minp[i * p] = p;
if (p == minp[i]) {
break;
}
}
}
}
constexpr int N = 30000;
std::vector<long double> ln(N + 1), dp(N + 1);
void solve() {
int n;
std::cin >> n;
std::cout << std::fixed << std::setprecision(8);
std::cout << dp[n] << '\n';
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
sieve(N);
for(int i = 1; i <= N; i ++ ) {
ln[i] = std::log(i);
}
for(auto e : primes) {
auto _dp = dp;
for(int i = e; i <= N; i *= e) {
for(int j = N; j >= i; j -- ) {
dp[j] = std::max(dp[j], _dp[j - i] + ln[i]);
}
}
std::vector<long double>().swap(_dp);
}
int T = 1;
std::cin >> T;
while(T -- ) {
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 235ms
memory: 4880kb
input:
3 2 7 10
output:
0.69314718 2.48490665 3.40119738
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 233ms
memory: 4892kb
input:
5000 580 4555 4654 1420 53 1076 1226 2733 2285 348 2104 2293 3447 4208 710 307 1763 1142 3027 2151 3182 1546 3398 867 2380 830 4211 3117 3058 2251 1890 3961 4003 3991 4167 4976 1765 3235 2644 4070 4644 3645 875 3005 4769 4934 3846 2941 255 946 4164 1372 1193 3056 4472 508 3949 2473 4490 88 4014 2953...
output:
59.80852192 202.44052577 204.28759887 102.51478785 12.79485881 87.11217775 94.28963296 150.93942420 135.93142462 44.13827326 130.23433114 135.99070123 171.94251616 192.93500649 67.65198476 40.42470119 116.70148327 90.46179229 159.83426584 131.02477723 164.22501826 108.28307964 170.87920165 76.825453...
result:
ok 5000 numbers
Test #3:
score: 0
Accepted
time: 244ms
memory: 4888kb
input:
30000 14727 26896 6571 17234 3891 15888 13803 8818 11068 5541 24029 24764 15463 20613 8526 102 23759 10980 24923 19706 25043 2014 15199 19085 5761 24243 2075 16490 695 29219 2397 17193 25700 12082 13253 4167 5329 23855 6274 13900 26056 2910 28712 13016 9531 3368 17801 24668 23566 28589 1630 29223 24...
output:
391.31375295 546.92510790 248.61417074 426.70126732 183.87310175 407.62670766 377.46405306 293.70697048 333.30526000 225.34129232 514.10943213 522.82162118 401.57570865 472.17792953 288.02946956 19.91624588 510.95883514 332.07204534 524.44003755 460.58106281 526.24282655 126.09778424 398.10346760 45...
result:
ok 30000 numbers
Test #4:
score: 0
Accepted
time: 245ms
memory: 5004kb
input:
30000 7303 9397 29807 14117 26079 521 24880 13348 3507 2730 12948 24124 11931 20353 2972 8842 2822 6482 28198 11160 20228 9360 22739 10345 6523 10943 1290 7656 25686 25672 5920 8709 21244 28654 14891 6931 13149 6285 25615 5220 26475 3569 4878 19879 17324 26596 20869 29746 22377 27326 10043 3099 1425...
output:
263.70719241 303.92395504 578.33186071 381.78939777 538.16566389 56.29697648 523.94024145 369.89878575 173.35813813 150.44428990 363.89821065 515.49572649 347.84399932 468.08629828 157.81896370 294.36806364 153.39411707 246.30311197 561.49104842 334.97355713 467.40175331 303.47527333 498.49626312 32...
result:
ok 30000 numbers
Test #5:
score: 0
Accepted
time: 240ms
memory: 4868kb
input:
30000 20346 25684 25448 20568 28450 22513 24535 22174 27365 29390 29947 26968 24429 29299 22646 24327 20884 28665 28165 26338 24932 24668 26276 26758 20761 20643 22023 21015 25086 24814 29117 20105 23995 25805 24808 26211 23715 20272 24108 21876 25946 20128 26304 27341 21729 28712 28003 29471 24643 ...
output:
468.06092694 533.04057984 530.39617966 471.31975838 564.28907499 496.06665763 520.01120685 492.14477878 551.80601229 574.27338413 580.59307750 548.06358053 518.60078214 573.53180195 497.73923288 517.51062951 475.01114287 566.43803368 561.43562487 540.97258299 524.49719597 521.78914577 540.07040184 5...
result:
ok 30000 numbers
Test #6:
score: 0
Accepted
time: 243ms
memory: 4884kb
input:
30000 29955 29983 29952 29905 29951 29929 29972 29954 29925 29932 29973 29965 29965 29963 29978 29914 29942 29906 29975 29901 29911 29952 29957 29903 29982 29982 29960 29917 29937 29915 29936 29976 29989 29900 29926 29923 29922 29976 29905 29995 29901 29952 29968 29954 29932 29971 29975 29936 29906 ...
output:
580.60681019 580.65761621 580.60422275 579.93830459 580.60030738 580.56347008 580.63949977 580.60681019 579.97549855 580.56680341 580.63949977 580.62460966 580.62460966 580.62021073 580.64943363 579.95628645 580.58704019 579.94129862 580.64205258 579.93146248 579.94890540 580.60422275 580.61037458 5...
result:
ok 30000 numbers
Extra Test:
score: 0
Extra Test Passed