답안 #490989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
490989	2021-11-30T02:55:36 Z	Mike4235	Toys (CEOI18_toy)	C++17	100 / 100	3489 ms	101012 KB

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
 
#include <bits/stdc++.h>
  
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
// #define int long long
 
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back
 
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
 
const long double PI = 3.1415926535897932384626433832795;
const int INF = 1000000000000000000;
const int MOD = 1000000007;
const int MOD2 = 1000000009;
const long double EPS = 1e-6;
 
using namespace std;
 
const int MX = 1e5;
 
int n;
unordered_map<int, vector<pii>> mp;
unordered_map<int, bool> flag;
set<int> se;
vector<pii> d[MX + 5];
 
void solve(int x, int sum) {
    if (flag[x * MOD + sum]) return;
    flag[x * MOD + sum] = 1;
    se.insert(sum + x - 1);
 
    if (x <= MX) {
        for (auto p : d[x]) solve(p.first, sum + p.second - 1);
        return;
    }
 
    if (mp.find(x) != mp.end()) {
        for (auto p : mp[x]) solve(p.first, sum + p.second - 1);
    }
    else {
        for (int i = 2; i * i <= x; i++) if (x % i == 0) {
            if (i * i == x) {
                mp[x].push_back({i, i});
                solve(i, sum + i - 1);
            }
            else {
                int j = x / i;
                mp[x].push_back({i, j});
                mp[x].push_back({j, i});
                solve(i, sum + j - 1);
                solve(j, sum + i - 1);
            }
        }
    }
}
 
signed main() {
    
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);
 
    for1(i,1,MX) {
        for (int j = i * 2, cnt = 2; j <= MX; j += i, cnt++) d[j].push_back({i, cnt});
    }
 
    cin >> n;
    solve(n, 0);
 
    cout << sz(se) << "\n";
    for (auto x : se) cout << x << " ";
    
}

Compilation message

toy.cpp:21:17: warning: overflow in conversion from 'long int' to 'int' changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
   21 | const int INF = 1000000000000000000;
      |                 ^~~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	79 ms	16156 KB	Output is correct
2	Correct	58 ms	16252 KB	Output is correct
3	Correct	59 ms	16244 KB	Output is correct
4	Correct	65 ms	16228 KB	Output is correct
5	Correct	56 ms	16252 KB	Output is correct
6	Correct	59 ms	16192 KB	Output is correct
7	Correct	59 ms	16180 KB	Output is correct
8	Correct	70 ms	16196 KB	Output is correct
9	Correct	77 ms	16172 KB	Output is correct
10	Correct	60 ms	16276 KB	Output is correct
11	Correct	55 ms	16196 KB	Output is correct
12	Correct	56 ms	16276 KB	Output is correct
13	Correct	66 ms	16276 KB	Output is correct
14	Correct	69 ms	16256 KB	Output is correct
15	Correct	78 ms	16212 KB	Output is correct
16	Correct	65 ms	16204 KB	Output is correct
17	Correct	73 ms	16272 KB	Output is correct
18	Correct	52 ms	16204 KB	Output is correct
19	Correct	60 ms	16260 KB	Output is correct
20	Correct	61 ms	16272 KB	Output is correct
21	Correct	63 ms	16168 KB	Output is correct
22	Correct	65 ms	16204 KB	Output is correct
23	Correct	62 ms	16252 KB	Output is correct
24	Correct	70 ms	16284 KB	Output is correct
25	Correct	64 ms	16376 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	79 ms	16156 KB	Output is correct
2	Correct	58 ms	16252 KB	Output is correct
3	Correct	59 ms	16244 KB	Output is correct
4	Correct	65 ms	16228 KB	Output is correct
5	Correct	56 ms	16252 KB	Output is correct
6	Correct	59 ms	16192 KB	Output is correct
7	Correct	59 ms	16180 KB	Output is correct
8	Correct	70 ms	16196 KB	Output is correct
9	Correct	77 ms	16172 KB	Output is correct
10	Correct	60 ms	16276 KB	Output is correct
11	Correct	55 ms	16196 KB	Output is correct
12	Correct	56 ms	16276 KB	Output is correct
13	Correct	66 ms	16276 KB	Output is correct
14	Correct	69 ms	16256 KB	Output is correct
15	Correct	78 ms	16212 KB	Output is correct
16	Correct	65 ms	16204 KB	Output is correct
17	Correct	73 ms	16272 KB	Output is correct
18	Correct	52 ms	16204 KB	Output is correct
19	Correct	60 ms	16260 KB	Output is correct
20	Correct	61 ms	16272 KB	Output is correct
21	Correct	63 ms	16168 KB	Output is correct
22	Correct	65 ms	16204 KB	Output is correct
23	Correct	62 ms	16252 KB	Output is correct
24	Correct	70 ms	16284 KB	Output is correct
25	Correct	64 ms	16376 KB	Output is correct
26	Correct	62 ms	16224 KB	Output is correct
27	Correct	63 ms	16192 KB	Output is correct
28	Correct	58 ms	16288 KB	Output is correct
29	Correct	57 ms	16284 KB	Output is correct
30	Correct	90 ms	16284 KB	Output is correct
31	Correct	65 ms	16196 KB	Output is correct
32	Correct	60 ms	16312 KB	Output is correct
33	Correct	57 ms	16256 KB	Output is correct
34	Correct	60 ms	16256 KB	Output is correct
35	Correct	63 ms	16180 KB	Output is correct
36	Correct	58 ms	16168 KB	Output is correct
37	Correct	78 ms	16252 KB	Output is correct
38	Correct	73 ms	16184 KB	Output is correct
39	Correct	60 ms	16180 KB	Output is correct
40	Correct	62 ms	16280 KB	Output is correct
41	Correct	57 ms	16280 KB	Output is correct
42	Correct	60 ms	16260 KB	Output is correct
43	Correct	62 ms	16228 KB	Output is correct
44	Correct	67 ms	16280 KB	Output is correct
45	Correct	65 ms	16276 KB	Output is correct
46	Correct	57 ms	16196 KB	Output is correct
47	Correct	58 ms	16248 KB	Output is correct
48	Correct	61 ms	16236 KB	Output is correct
49	Correct	84 ms	16168 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	79 ms	16156 KB	Output is correct
2	Correct	58 ms	16252 KB	Output is correct
3	Correct	59 ms	16244 KB	Output is correct
4	Correct	65 ms	16228 KB	Output is correct
5	Correct	56 ms	16252 KB	Output is correct
6	Correct	59 ms	16192 KB	Output is correct
7	Correct	59 ms	16180 KB	Output is correct
8	Correct	70 ms	16196 KB	Output is correct
9	Correct	77 ms	16172 KB	Output is correct
10	Correct	60 ms	16276 KB	Output is correct
11	Correct	55 ms	16196 KB	Output is correct
12	Correct	56 ms	16276 KB	Output is correct
13	Correct	66 ms	16276 KB	Output is correct
14	Correct	69 ms	16256 KB	Output is correct
15	Correct	78 ms	16212 KB	Output is correct
16	Correct	65 ms	16204 KB	Output is correct
17	Correct	73 ms	16272 KB	Output is correct
18	Correct	52 ms	16204 KB	Output is correct
19	Correct	60 ms	16260 KB	Output is correct
20	Correct	61 ms	16272 KB	Output is correct
21	Correct	63 ms	16168 KB	Output is correct
22	Correct	65 ms	16204 KB	Output is correct
23	Correct	62 ms	16252 KB	Output is correct
24	Correct	70 ms	16284 KB	Output is correct
25	Correct	64 ms	16376 KB	Output is correct
26	Correct	62 ms	16224 KB	Output is correct
27	Correct	63 ms	16192 KB	Output is correct
28	Correct	58 ms	16288 KB	Output is correct
29	Correct	57 ms	16284 KB	Output is correct
30	Correct	90 ms	16284 KB	Output is correct
31	Correct	65 ms	16196 KB	Output is correct
32	Correct	60 ms	16312 KB	Output is correct
33	Correct	57 ms	16256 KB	Output is correct
34	Correct	60 ms	16256 KB	Output is correct
35	Correct	63 ms	16180 KB	Output is correct
36	Correct	58 ms	16168 KB	Output is correct
37	Correct	78 ms	16252 KB	Output is correct
38	Correct	73 ms	16184 KB	Output is correct
39	Correct	60 ms	16180 KB	Output is correct
40	Correct	62 ms	16280 KB	Output is correct
41	Correct	57 ms	16280 KB	Output is correct
42	Correct	60 ms	16260 KB	Output is correct
43	Correct	62 ms	16228 KB	Output is correct
44	Correct	67 ms	16280 KB	Output is correct
45	Correct	65 ms	16276 KB	Output is correct
46	Correct	57 ms	16196 KB	Output is correct
47	Correct	58 ms	16248 KB	Output is correct
48	Correct	61 ms	16236 KB	Output is correct
49	Correct	84 ms	16168 KB	Output is correct
50	Correct	69 ms	16388 KB	Output is correct
51	Correct	63 ms	16392 KB	Output is correct
52	Correct	67 ms	16364 KB	Output is correct
53	Correct	58 ms	16324 KB	Output is correct
54	Correct	62 ms	16304 KB	Output is correct
55	Correct	62 ms	16404 KB	Output is correct
56	Correct	58 ms	16324 KB	Output is correct
57	Correct	64 ms	16496 KB	Output is correct
58	Correct	61 ms	16288 KB	Output is correct
59	Correct	58 ms	16192 KB	Output is correct
60	Correct	59 ms	16244 KB	Output is correct
61	Correct	57 ms	16320 KB	Output is correct
62	Correct	56 ms	16284 KB	Output is correct
63	Correct	66 ms	16220 KB	Output is correct
64	Correct	82 ms	16180 KB	Output is correct
65	Correct	64 ms	16280 KB	Output is correct
66	Correct	55 ms	16196 KB	Output is correct
67	Correct	59 ms	16180 KB	Output is correct
68	Correct	58 ms	16280 KB	Output is correct
69	Correct	57 ms	16180 KB	Output is correct
70	Correct	64 ms	16196 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	79 ms	16156 KB	Output is correct
2	Correct	58 ms	16252 KB	Output is correct
3	Correct	59 ms	16244 KB	Output is correct
4	Correct	65 ms	16228 KB	Output is correct
5	Correct	56 ms	16252 KB	Output is correct
6	Correct	59 ms	16192 KB	Output is correct
7	Correct	59 ms	16180 KB	Output is correct
8	Correct	70 ms	16196 KB	Output is correct
9	Correct	77 ms	16172 KB	Output is correct
10	Correct	60 ms	16276 KB	Output is correct
11	Correct	55 ms	16196 KB	Output is correct
12	Correct	56 ms	16276 KB	Output is correct
13	Correct	66 ms	16276 KB	Output is correct
14	Correct	69 ms	16256 KB	Output is correct
15	Correct	78 ms	16212 KB	Output is correct
16	Correct	65 ms	16204 KB	Output is correct
17	Correct	73 ms	16272 KB	Output is correct
18	Correct	52 ms	16204 KB	Output is correct
19	Correct	60 ms	16260 KB	Output is correct
20	Correct	61 ms	16272 KB	Output is correct
21	Correct	63 ms	16168 KB	Output is correct
22	Correct	65 ms	16204 KB	Output is correct
23	Correct	62 ms	16252 KB	Output is correct
24	Correct	70 ms	16284 KB	Output is correct
25	Correct	64 ms	16376 KB	Output is correct
26	Correct	62 ms	16224 KB	Output is correct
27	Correct	63 ms	16192 KB	Output is correct
28	Correct	58 ms	16288 KB	Output is correct
29	Correct	57 ms	16284 KB	Output is correct
30	Correct	90 ms	16284 KB	Output is correct
31	Correct	65 ms	16196 KB	Output is correct
32	Correct	60 ms	16312 KB	Output is correct
33	Correct	57 ms	16256 KB	Output is correct
34	Correct	60 ms	16256 KB	Output is correct
35	Correct	63 ms	16180 KB	Output is correct
36	Correct	58 ms	16168 KB	Output is correct
37	Correct	78 ms	16252 KB	Output is correct
38	Correct	73 ms	16184 KB	Output is correct
39	Correct	60 ms	16180 KB	Output is correct
40	Correct	62 ms	16280 KB	Output is correct
41	Correct	57 ms	16280 KB	Output is correct
42	Correct	60 ms	16260 KB	Output is correct
43	Correct	62 ms	16228 KB	Output is correct
44	Correct	67 ms	16280 KB	Output is correct
45	Correct	65 ms	16276 KB	Output is correct
46	Correct	57 ms	16196 KB	Output is correct
47	Correct	58 ms	16248 KB	Output is correct
48	Correct	61 ms	16236 KB	Output is correct
49	Correct	84 ms	16168 KB	Output is correct
50	Correct	69 ms	16388 KB	Output is correct
51	Correct	63 ms	16392 KB	Output is correct
52	Correct	67 ms	16364 KB	Output is correct
53	Correct	58 ms	16324 KB	Output is correct
54	Correct	62 ms	16304 KB	Output is correct
55	Correct	62 ms	16404 KB	Output is correct
56	Correct	58 ms	16324 KB	Output is correct
57	Correct	64 ms	16496 KB	Output is correct
58	Correct	61 ms	16288 KB	Output is correct
59	Correct	58 ms	16192 KB	Output is correct
60	Correct	59 ms	16244 KB	Output is correct
61	Correct	57 ms	16320 KB	Output is correct
62	Correct	56 ms	16284 KB	Output is correct
63	Correct	66 ms	16220 KB	Output is correct
64	Correct	82 ms	16180 KB	Output is correct
65	Correct	64 ms	16280 KB	Output is correct
66	Correct	55 ms	16196 KB	Output is correct
67	Correct	59 ms	16180 KB	Output is correct
68	Correct	58 ms	16280 KB	Output is correct
69	Correct	57 ms	16180 KB	Output is correct
70	Correct	64 ms	16196 KB	Output is correct
71	Correct	472 ms	36160 KB	Output is correct
72	Correct	327 ms	28564 KB	Output is correct
73	Correct	366 ms	30168 KB	Output is correct
74	Correct	238 ms	26392 KB	Output is correct
75	Correct	275 ms	26804 KB	Output is correct
76	Correct	678 ms	39132 KB	Output is correct
77	Correct	660 ms	36904 KB	Output is correct
78	Correct	624 ms	36164 KB	Output is correct
79	Correct	513 ms	35980 KB	Output is correct
80	Correct	65 ms	16408 KB	Output is correct
81	Correct	60 ms	16332 KB	Output is correct
82	Correct	64 ms	16332 KB	Output is correct
83	Correct	93 ms	18708 KB	Output is correct
84	Correct	111 ms	20544 KB	Output is correct
85	Correct	76 ms	16904 KB	Output is correct
86	Correct	66 ms	16196 KB	Output is correct
87	Correct	126 ms	20708 KB	Output is correct
88	Correct	59 ms	16244 KB	Output is correct
89	Correct	64 ms	16276 KB	Output is correct
90	Correct	59 ms	16196 KB	Output is correct
91	Correct	93 ms	17416 KB	Output is correct
92	Correct	134 ms	21928 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	79 ms	16156 KB	Output is correct
2	Correct	58 ms	16252 KB	Output is correct
3	Correct	59 ms	16244 KB	Output is correct
4	Correct	65 ms	16228 KB	Output is correct
5	Correct	56 ms	16252 KB	Output is correct
6	Correct	59 ms	16192 KB	Output is correct
7	Correct	59 ms	16180 KB	Output is correct
8	Correct	70 ms	16196 KB	Output is correct
9	Correct	77 ms	16172 KB	Output is correct
10	Correct	60 ms	16276 KB	Output is correct
11	Correct	55 ms	16196 KB	Output is correct
12	Correct	56 ms	16276 KB	Output is correct
13	Correct	66 ms	16276 KB	Output is correct
14	Correct	69 ms	16256 KB	Output is correct
15	Correct	78 ms	16212 KB	Output is correct
16	Correct	65 ms	16204 KB	Output is correct
17	Correct	73 ms	16272 KB	Output is correct
18	Correct	52 ms	16204 KB	Output is correct
19	Correct	60 ms	16260 KB	Output is correct
20	Correct	61 ms	16272 KB	Output is correct
21	Correct	63 ms	16168 KB	Output is correct
22	Correct	65 ms	16204 KB	Output is correct
23	Correct	62 ms	16252 KB	Output is correct
24	Correct	70 ms	16284 KB	Output is correct
25	Correct	64 ms	16376 KB	Output is correct
26	Correct	62 ms	16224 KB	Output is correct
27	Correct	63 ms	16192 KB	Output is correct
28	Correct	58 ms	16288 KB	Output is correct
29	Correct	57 ms	16284 KB	Output is correct
30	Correct	90 ms	16284 KB	Output is correct
31	Correct	65 ms	16196 KB	Output is correct
32	Correct	60 ms	16312 KB	Output is correct
33	Correct	57 ms	16256 KB	Output is correct
34	Correct	60 ms	16256 KB	Output is correct
35	Correct	63 ms	16180 KB	Output is correct
36	Correct	58 ms	16168 KB	Output is correct
37	Correct	78 ms	16252 KB	Output is correct
38	Correct	73 ms	16184 KB	Output is correct
39	Correct	60 ms	16180 KB	Output is correct
40	Correct	62 ms	16280 KB	Output is correct
41	Correct	57 ms	16280 KB	Output is correct
42	Correct	60 ms	16260 KB	Output is correct
43	Correct	62 ms	16228 KB	Output is correct
44	Correct	67 ms	16280 KB	Output is correct
45	Correct	65 ms	16276 KB	Output is correct
46	Correct	57 ms	16196 KB	Output is correct
47	Correct	58 ms	16248 KB	Output is correct
48	Correct	61 ms	16236 KB	Output is correct
49	Correct	84 ms	16168 KB	Output is correct
50	Correct	69 ms	16388 KB	Output is correct
51	Correct	63 ms	16392 KB	Output is correct
52	Correct	67 ms	16364 KB	Output is correct
53	Correct	58 ms	16324 KB	Output is correct
54	Correct	62 ms	16304 KB	Output is correct
55	Correct	62 ms	16404 KB	Output is correct
56	Correct	58 ms	16324 KB	Output is correct
57	Correct	64 ms	16496 KB	Output is correct
58	Correct	61 ms	16288 KB	Output is correct
59	Correct	58 ms	16192 KB	Output is correct
60	Correct	59 ms	16244 KB	Output is correct
61	Correct	57 ms	16320 KB	Output is correct
62	Correct	56 ms	16284 KB	Output is correct
63	Correct	66 ms	16220 KB	Output is correct
64	Correct	82 ms	16180 KB	Output is correct
65	Correct	64 ms	16280 KB	Output is correct
66	Correct	55 ms	16196 KB	Output is correct
67	Correct	59 ms	16180 KB	Output is correct
68	Correct	58 ms	16280 KB	Output is correct
69	Correct	57 ms	16180 KB	Output is correct
70	Correct	64 ms	16196 KB	Output is correct
71	Correct	472 ms	36160 KB	Output is correct
72	Correct	327 ms	28564 KB	Output is correct
73	Correct	366 ms	30168 KB	Output is correct
74	Correct	238 ms	26392 KB	Output is correct
75	Correct	275 ms	26804 KB	Output is correct
76	Correct	678 ms	39132 KB	Output is correct
77	Correct	660 ms	36904 KB	Output is correct
78	Correct	624 ms	36164 KB	Output is correct
79	Correct	513 ms	35980 KB	Output is correct
80	Correct	65 ms	16408 KB	Output is correct
81	Correct	60 ms	16332 KB	Output is correct
82	Correct	64 ms	16332 KB	Output is correct
83	Correct	93 ms	18708 KB	Output is correct
84	Correct	111 ms	20544 KB	Output is correct
85	Correct	76 ms	16904 KB	Output is correct
86	Correct	66 ms	16196 KB	Output is correct
87	Correct	126 ms	20708 KB	Output is correct
88	Correct	59 ms	16244 KB	Output is correct
89	Correct	64 ms	16276 KB	Output is correct
90	Correct	59 ms	16196 KB	Output is correct
91	Correct	93 ms	17416 KB	Output is correct
92	Correct	134 ms	21928 KB	Output is correct
93	Correct	3097 ms	99260 KB	Output is correct
94	Correct	1656 ms	64900 KB	Output is correct
95	Correct	1743 ms	66652 KB	Output is correct
96	Correct	1577 ms	62328 KB	Output is correct
97	Correct	1448 ms	59192 KB	Output is correct
98	Correct	3261 ms	100028 KB	Output is correct
99	Correct	3489 ms	101012 KB	Output is correct
100	Correct	3195 ms	99208 KB	Output is correct
101	Correct	2997 ms	99048 KB	Output is correct
102	Correct	2669 ms	99004 KB	Output is correct
103	Correct	2125 ms	72104 KB	Output is correct
104	Correct	58 ms	16260 KB	Output is correct
105	Correct	57 ms	16272 KB	Output is correct
106	Correct	61 ms	16556 KB	Output is correct
107	Correct	195 ms	25740 KB	Output is correct
108	Correct	508 ms	36200 KB	Output is correct
109	Correct	88 ms	18484 KB	Output is correct
110	Correct	58 ms	16280 KB	Output is correct
111	Correct	242 ms	27276 KB	Output is correct
112	Correct	62 ms	16328 KB	Output is correct
113	Correct	56 ms	16236 KB	Output is correct
114	Correct	63 ms	16536 KB	Output is correct
115	Correct	60 ms	16200 KB	Output is correct
116	Correct	71 ms	17048 KB	Output is correct
117	Correct	524 ms	39588 KB	Output is correct

답안 #490989

Compilation message

Subtask #1 19.0 / 19.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 20.0 / 20.0

Subtask #5 21.0 / 21.0

Subtask #1
19.0 / 19.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
20.0 / 20.0

Subtask #5
21.0 / 21.0