QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#578396#9307. Clock MastershiftAC ✓245ms5004kbC++205.6kb2024-09-20 18:52:202024-09-20 18:52:20

Judging History

你现在查看的是最新测评结果

  • [2024-09-20 18:52:20]
  • 评测
  • 测评结果:AC
  • 用时:245ms
  • 内存:5004kb
  • [2024-09-20 18:52:20]
  • 提交

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,我给组数据试试?

详细

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