제출 #1236808

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236808		yassia	Toys (CEOI18_toy)	C++20	79 / 100	5094 ms	47240 KiB

toy

#ifndef local
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = int;
using pll = pair<ll,ll>;
using str = string;
using ld = long double;
auto sd = std::chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(sd);

using ordset = tree<pll, null_type,less<>, rb_tree_tag,tree_order_statistics_node_update>;
struct pair_hsh {
    template <class t1, class t2>
    size_t operator()(const pair<t1, t2> &pp)const {
        auto h1 = hash<t1>{}(pp.first);
        auto h2 = hash<t2>{}(pp.second);
        return h1^(h2<<1);
    }
};

vector<ll> answ;
map<ll,vector<ll>> divs;
set<pll> c;
void rec(ll cur, ll ans) {
    c.insert({cur, ans});
    if (cur==1) {
        answ.emplace_back(ans);
        return;
    }
    if (divs[cur].empty()){
        for (int d = 1; d*d <= cur; d++) {
            if ((cur / d)*d == cur) {
                divs[cur].emplace_back(d);
                if (c.find({d, ans+cur/d-1})==c.end()){
                    rec(d, ans+cur/d-1);
                }
                if (cur / d == d)continue;
                divs[cur].emplace_back(cur/d);
                if (c.find({cur/d, ans+d-1})==c.end()){
                    rec(cur/d, ans+d-1);
                }
            }
        }
    }
    else {
        for (auto d: divs[cur]){
            if (c.find({d, ans+cur/d-1})==c.end()){
                rec(d, ans+cur/d-1);
            }
            if (cur / d == d)continue;
            if (c.find({cur/d, ans+d-1})==c.end()){
                rec(cur/d, ans+d-1);
            }
        }

    }

}
void solve1() {
    ll n;
    cin >> n;
    rec(n, 0);
    sort(answ.begin(), answ.end());
    cout<<answ.size()<<'\n';
    for (auto x: answ) cout<<x<<" ";
    cout<<endl;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#ifdef local
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ll t1 = 1;
    //cin>>t1;
    for (int _ = 0; _ < t1; ++_) solve1();
#ifdef local
    printf_s("\n%.5f s", (double) clock() / CLOCKS_PER_SEC);
#endif
}

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