oj.uz

Submission #866300

# Submission time Handle Problem Language Result Execution time Memory
866300 2023-10-25T19:18:45 Z themm1 Toys (CEOI18_toy) C++17
59 / 100
 45 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
// ordered set whith s.order_of_key(x) method, which returns rank of element x in set s
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
*/

// pair printing
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "(" << par.first << "; " << par.second << ")"; return out;}
// set printing
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for(const auto &x:cont) out << x << ", "; out << "}"; return out; }
// map printing
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for(const auto &x:cont) out << x << ", "; out << "}"; return out; }
// unordered_set printing
template <class T>
ostream& operator<<(ostream& out, const unordered_set<T> &cont) {out << "{";for(const auto &x:cont) out << x << ", ";out << "}";return out;}
// unordered_map printing
template <class T, class U>
ostream& operator<<(ostream& out, const unordered_map<T, U> &cont) {out << "{";for(const auto &x:cont) out << x << ", ";out << "}";return out;}
// vector printing
template<class T>
ostream& operator<<(ostream& out, const vector<T> &cont){ out << "[";  for (const auto &x:cont) out << x << ", ";  out << "]"; return out;}

#define print(x) cout << (x) << endl;
#define dmp(x) cerr << #x << " = " << x << endl
#define dmpn(x) cerr << #x << " = " << x << "; "
#define dmpl(x) cerr << "Line " << __LINE__ << ": " << #x << " = " << x << endl

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define contains(s,x) ((s).find(x) != (s).end())
const int MOD = 998244353;

void solve() {
        int N;
        cin >> N;
        if (N == 1) {
                cout << 1 << endl;
                cout << 0 << endl;
                return;
        }
        vector<set<pii>> m(N + 1);
        set<int> ds;
        for (int i = 1; i < sqrt(N) + 1; i++) if (N % i == 0) {
                ds.insert(i);
                ds.insert(N / i);
        }
        vector<int> divisors(all(ds));
        for (int a : divisors) {
                if (a == 1) continue;
                int mx = sqrt(a) + 1;
                m[a].insert({ 1, a });
                for (int x : divisors) {
                        if (x >= mx) break;
                        if (a % x != 0) continue;
                        int y = a / x;
                        for (pii p1 : m[x]) for (pii p2 : m[y]) {
                                m[a].insert({ p1.ff + p2.ff, p1.ss + p2.ss });
                        }
                }
        }
        /*
        for (auto kv : m) {
                cout << kv.ff << ": " << kv.ss << endl;
        }
        */
        set<int> answer;
        for (pii p : m[N]) answer.insert(p.ss - p.ff);
        cout << sz(answer) << endl;
        for (int a : answer) cout << a << " ";
        cout << endl;

}

int32_t main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);

        int t = 1;
        // cin >> t;
        while (t--) {
                solve();
        }
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 856 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 2 ms 860 KB Output is correct
32 Correct 1 ms 896 KB Output is correct
33 Correct 1 ms 860 KB Output is correct
34 Correct 1 ms 1112 KB Output is correct
35 Correct 1 ms 1112 KB Output is correct
36 Correct 1 ms 860 KB Output is correct
37 Correct 1 ms 896 KB Output is correct
38 Correct 1 ms 860 KB Output is correct
39 Correct 0 ms 860 KB Output is correct
40 Correct 1 ms 860 KB Output is correct
41 Correct 1 ms 860 KB Output is correct
42 Correct 1 ms 684 KB Output is correct
43 Correct 1 ms 860 KB Output is correct
44 Correct 0 ms 860 KB Output is correct
45 Correct 1 ms 860 KB Output is correct
46 Correct 0 ms 860 KB Output is correct
47 Correct 1 ms 856 KB Output is correct
48 Correct 1 ms 860 KB Output is correct
49 Correct 0 ms 860 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 856 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 2 ms 860 KB Output is correct
32 Correct 1 ms 896 KB Output is correct
33 Correct 1 ms 860 KB Output is correct
34 Correct 1 ms 1112 KB Output is correct
35 Correct 1 ms 1112 KB Output is correct
36 Correct 1 ms 860 KB Output is correct
37 Correct 1 ms 896 KB Output is correct
38 Correct 1 ms 860 KB Output is correct
39 Correct 0 ms 860 KB Output is correct
40 Correct 1 ms 860 KB Output is correct
41 Correct 1 ms 860 KB Output is correct
42 Correct 1 ms 684 KB Output is correct
43 Correct 1 ms 860 KB Output is correct
44 Correct 0 ms 860 KB Output is correct
45 Correct 1 ms 860 KB Output is correct
46 Correct 0 ms 860 KB Output is correct
47 Correct 1 ms 856 KB Output is correct
48 Correct 1 ms 860 KB Output is correct
49 Correct 0 ms 860 KB Output is correct
50 Correct 6 ms 4696 KB Output is correct
51 Correct 6 ms 3420 KB Output is correct
52 Correct 7 ms 2972 KB Output is correct
53 Correct 6 ms 2908 KB Output is correct
54 Correct 3 ms 1884 KB Output is correct
55 Correct 15 ms 5212 KB Output is correct
56 Correct 13 ms 4700 KB Output is correct
57 Correct 9 ms 4368 KB Output is correct
58 Correct 2 ms 4956 KB Output is correct
59 Correct 1 ms 4956 KB Output is correct
60 Correct 1 ms 3420 KB Output is correct
61 Correct 8 ms 4984 KB Output is correct
62 Correct 2 ms 1628 KB Output is correct
63 Correct 2 ms 5212 KB Output is correct
64 Correct 1 ms 4952 KB Output is correct
65 Correct 5 ms 4956 KB Output is correct
66 Correct 1 ms 4956 KB Output is correct
67 Correct 2 ms 4956 KB Output is correct
68 Correct 2 ms 4956 KB Output is correct
69 Correct 2 ms 4956 KB Output is correct
70 Correct 3 ms 4700 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 856 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 2 ms 860 KB Output is correct
32 Correct 1 ms 896 KB Output is correct
33 Correct 1 ms 860 KB Output is correct
34 Correct 1 ms 1112 KB Output is correct
35 Correct 1 ms 1112 KB Output is correct
36 Correct 1 ms 860 KB Output is correct
37 Correct 1 ms 896 KB Output is correct
38 Correct 1 ms 860 KB Output is correct
39 Correct 0 ms 860 KB Output is correct
40 Correct 1 ms 860 KB Output is correct
41 Correct 1 ms 860 KB Output is correct
42 Correct 1 ms 684 KB Output is correct
43 Correct 1 ms 860 KB Output is correct
44 Correct 0 ms 860 KB Output is correct
45 Correct 1 ms 860 KB Output is correct
46 Correct 0 ms 860 KB Output is correct
47 Correct 1 ms 856 KB Output is correct
48 Correct 1 ms 860 KB Output is correct
49 Correct 0 ms 860 KB Output is correct
50 Correct 6 ms 4696 KB Output is correct
51 Correct 6 ms 3420 KB Output is correct
52 Correct 7 ms 2972 KB Output is correct
53 Correct 6 ms 2908 KB Output is correct
54 Correct 3 ms 1884 KB Output is correct
55 Correct 15 ms 5212 KB Output is correct
56 Correct 13 ms 4700 KB Output is correct
57 Correct 9 ms 4368 KB Output is correct
58 Correct 2 ms 4956 KB Output is correct
59 Correct 1 ms 4956 KB Output is correct
60 Correct 1 ms 3420 KB Output is correct
61 Correct 8 ms 4984 KB Output is correct
62 Correct 2 ms 1628 KB Output is correct
63 Correct 2 ms 5212 KB Output is correct
64 Correct 1 ms 4952 KB Output is correct
65 Correct 5 ms 4956 KB Output is correct
66 Correct 1 ms 4956 KB Output is correct
67 Correct 2 ms 4956 KB Output is correct
68 Correct 2 ms 4956 KB Output is correct
69 Correct 2 ms 4956 KB Output is correct
70 Correct 3 ms 4700 KB Output is correct
71 Runtime error 45 ms 262144 KB Execution killed with signal 9
72 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 856 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 2 ms 860 KB Output is correct
32 Correct 1 ms 896 KB Output is correct
33 Correct 1 ms 860 KB Output is correct
34 Correct 1 ms 1112 KB Output is correct
35 Correct 1 ms 1112 KB Output is correct
36 Correct 1 ms 860 KB Output is correct
37 Correct 1 ms 896 KB Output is correct
38 Correct 1 ms 860 KB Output is correct
39 Correct 0 ms 860 KB Output is correct
40 Correct 1 ms 860 KB Output is correct
41 Correct 1 ms 860 KB Output is correct
42 Correct 1 ms 684 KB Output is correct
43 Correct 1 ms 860 KB Output is correct
44 Correct 0 ms 860 KB Output is correct
45 Correct 1 ms 860 KB Output is correct
46 Correct 0 ms 860 KB Output is correct
47 Correct 1 ms 856 KB Output is correct
48 Correct 1 ms 860 KB Output is correct
49 Correct 0 ms 860 KB Output is correct
50 Correct 6 ms 4696 KB Output is correct
51 Correct 6 ms 3420 KB Output is correct
52 Correct 7 ms 2972 KB Output is correct
53 Correct 6 ms 2908 KB Output is correct
54 Correct 3 ms 1884 KB Output is correct
55 Correct 15 ms 5212 KB Output is correct
56 Correct 13 ms 4700 KB Output is correct
57 Correct 9 ms 4368 KB Output is correct
58 Correct 2 ms 4956 KB Output is correct
59 Correct 1 ms 4956 KB Output is correct
60 Correct 1 ms 3420 KB Output is correct
61 Correct 8 ms 4984 KB Output is correct
62 Correct 2 ms 1628 KB Output is correct
63 Correct 2 ms 5212 KB Output is correct
64 Correct 1 ms 4952 KB Output is correct
65 Correct 5 ms 4956 KB Output is correct
66 Correct 1 ms 4956 KB Output is correct
67 Correct 2 ms 4956 KB Output is correct
68 Correct 2 ms 4956 KB Output is correct
69 Correct 2 ms 4956 KB Output is correct
70 Correct 3 ms 4700 KB Output is correct
71 Runtime error 45 ms 262144 KB Execution killed with signal 9
72 Halted 0 ms 0 KB -