Submission #104955

#	Time	Username	Problem	Language	Result	Execution time	Memory
104955		eriksuenderhauf	Toys (CEOI18_toy)	C++11	100 / 100	3169 ms	109816 KiB

toy

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,null_type,hash<int>> ht2;
typedef cc_hash_table<int,ht2,hash<int>> ht;
ht dp;
int di[100000];
int m = 0;

ht2 dfs(int n) {
    if (dp.find(n) != dp.end())
        return dp[n];
    if (n == 1) {
        ht2 sm;
        sm.insert(0);
        dp[n] = sm;
        return sm;
    }
    ht2 ret;
    ret.insert(n - 1);
    for (int j = 0; j < m; j++) {
        int i = di[j];
        if (i * i > n)
            break;
        if (n % i != 0)
            continue;
        ht2 tmp = dfs(n / i);
        auto it = tmp.begin();
        for (; it != tmp.end(); it++)
            ret.insert((*it) + i - 1);
    }
    dp[n] = ret;
    return ret;
}

int main()
{
    int n;
    ni(n);
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
            di[m++] = i;
    ht2 sm = dfs(n);
    m = 0;
    printf("%d\n", sm.size());
    auto it = sm.begin();
    for (; it != sm.end(); it++)
        di[m++] = *it;
    sort(di, di + m);
    for (int i = 0; i < m; i++)
        printf("%d ", di[i]);
    enl;
    return 0;
}

Compilation message (stderr)

toy.cpp: In function 'int main()':
toy.cpp:57:29: warning: format '%d' expects argument of type 'int', but argument 2 has type '__gnu_pbds::detail::cc_ht_set<int, __gnu_pbds::null_type, std::hash<int>, std::equal_to<int>, std::allocator<char>, false, __gnu_pbds::direct_mask_range_hashing<>, __gnu_pbds::hash_standard_resize_policy<__gnu_pbds::hash_exponential_size_policy<>, __gnu_pbds::hash_load_check_resize_trigger<>, false, long unsigned int> >::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", sm.size());
                    ~~~~~~~~~^
toy.cpp:7:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &(n))
               ~~~~~^~~~~~~~~~~~
toy.cpp:51:5: note: in expansion of macro 'ni'
     ni(n);
     ^~

• Subtask 1: 19 / 19
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 21 / 21