답안 #50910 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50910	2018-06-14T16:27:32 Z	Nicksechko	Nice sequence (IZhO18_sequence)	C++14	100 / 100	710 ms	42184 KB

sequence

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using namespace std;

const int MAXN = 400001;

bool w[MAXN];
int ans;
int a[MAXN];
int t;
int n, m;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

void dfs(int v) {
    if (v < 0 || v > ans || w[v]) {
        return;
    }

    w[v] = true;
    dfs(v - n);
    dfs(v + m);
    
    a[v] = t++;
}

void solve() {
    cin >> n >> m;
    ans = n + m - gcd(n, m) - 1;
    t = 0;
    fill(w, w + ans + 1, false);

    for (int i = 0; i <= ans; ++i) {
        dfs(i);
    }

    cout << ans << "\n";
    for (int i = 0; i < ans; ++i) {
        cout << a[i] - a[i + 1] << " ";
    }

    cout << "\n";
}

int main() {
#ifdef PAUNSVOKNO
    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(20); cout.tie(nullptr); cin.tie(nullptr);
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Ok
2	Correct	2 ms	376 KB	Ok
3	Correct	2 ms	472 KB	Ok
4	Correct	3 ms	584 KB	Ok
5	Correct	2 ms	636 KB	Ok
6	Correct	2 ms	640 KB	Ok
7	Correct	2 ms	704 KB	Ok
8	Correct	2 ms	708 KB	Ok
9	Correct	2 ms	712 KB	Ok
10	Correct	3 ms	716 KB	Ok
11	Correct	3 ms	720 KB	Ok
12	Correct	2 ms	724 KB	Ok

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	728 KB	Ok
2	Correct	3 ms	744 KB	Ok
3	Correct	3 ms	900 KB	Ok
4	Correct	2 ms	900 KB	Ok
5	Correct	2 ms	900 KB	Ok
6	Correct	4 ms	908 KB	Ok
7	Correct	10 ms	1316 KB	Ok
8	Correct	7 ms	1316 KB	Ok
9	Correct	12 ms	1484 KB	Ok
10	Correct	8 ms	1484 KB	Ok

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1484 KB	Ok
2	Correct	2 ms	1484 KB	Ok
3	Correct	3 ms	1484 KB	Ok
4	Correct	2 ms	1484 KB	Ok
5	Correct	2 ms	1484 KB	Ok
6	Correct	2 ms	1484 KB	Ok
7	Correct	3 ms	1484 KB	Ok
8	Correct	2 ms	1484 KB	Ok
9	Correct	3 ms	1484 KB	Ok
10	Correct	2 ms	1484 KB	Ok
11	Correct	2 ms	1484 KB	Ok

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1484 KB	Ok
2	Correct	2 ms	1484 KB	Ok
3	Correct	2 ms	1484 KB	Ok
4	Correct	2 ms	1484 KB	Ok
5	Correct	3 ms	1484 KB	Ok
6	Correct	78 ms	9896 KB	Ok
7	Correct	73 ms	9896 KB	Ok
8	Correct	137 ms	11564 KB	Ok
9	Correct	135 ms	11564 KB	Ok
10	Correct	69 ms	11564 KB	Ok
11	Correct	171 ms	12744 KB	Ok

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Ok
2	Correct	2 ms	376 KB	Ok
3	Correct	2 ms	472 KB	Ok
4	Correct	3 ms	584 KB	Ok
5	Correct	2 ms	636 KB	Ok
6	Correct	2 ms	640 KB	Ok
7	Correct	2 ms	704 KB	Ok
8	Correct	2 ms	708 KB	Ok
9	Correct	2 ms	712 KB	Ok
10	Correct	3 ms	716 KB	Ok
11	Correct	3 ms	720 KB	Ok
12	Correct	2 ms	724 KB	Ok
13	Correct	3 ms	1484 KB	Ok
14	Correct	2 ms	1484 KB	Ok
15	Correct	3 ms	1484 KB	Ok
16	Correct	2 ms	1484 KB	Ok
17	Correct	2 ms	1484 KB	Ok
18	Correct	2 ms	1484 KB	Ok
19	Correct	3 ms	1484 KB	Ok
20	Correct	2 ms	1484 KB	Ok
21	Correct	3 ms	1484 KB	Ok
22	Correct	2 ms	1484 KB	Ok
23	Correct	2 ms	1484 KB	Ok
24	Correct	5 ms	12744 KB	Ok
25	Correct	4 ms	12744 KB	Ok
26	Correct	4 ms	12744 KB	Ok
27	Correct	4 ms	12744 KB	Ok
28	Correct	3 ms	12744 KB	Ok
29	Correct	3 ms	12744 KB	Ok
30	Correct	3 ms	12744 KB	Ok
31	Correct	7 ms	12744 KB	Ok
32	Correct	6 ms	12744 KB	Ok
33	Correct	5 ms	12744 KB	Ok
34	Correct	7 ms	12744 KB	Ok
35	Correct	6 ms	12744 KB	Ok
36	Correct	7 ms	12744 KB	Ok
37	Correct	6 ms	12744 KB	Ok
38	Correct	6 ms	12744 KB	Ok
39	Correct	5 ms	12744 KB	Ok
40	Correct	6 ms	12744 KB	Ok
41	Correct	5 ms	12744 KB	Ok
42	Correct	7 ms	12744 KB	Ok
43	Correct	10 ms	12744 KB	Ok

Subtask #6
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Ok
2	Correct	2 ms	376 KB	Ok
3	Correct	2 ms	472 KB	Ok
4	Correct	3 ms	584 KB	Ok
5	Correct	2 ms	636 KB	Ok
6	Correct	2 ms	640 KB	Ok
7	Correct	2 ms	704 KB	Ok
8	Correct	2 ms	708 KB	Ok
9	Correct	2 ms	712 KB	Ok
10	Correct	3 ms	716 KB	Ok
11	Correct	3 ms	720 KB	Ok
12	Correct	2 ms	724 KB	Ok
13	Correct	3 ms	728 KB	Ok
14	Correct	3 ms	744 KB	Ok
15	Correct	3 ms	900 KB	Ok
16	Correct	2 ms	900 KB	Ok
17	Correct	2 ms	900 KB	Ok
18	Correct	4 ms	908 KB	Ok
19	Correct	10 ms	1316 KB	Ok
20	Correct	7 ms	1316 KB	Ok
21	Correct	12 ms	1484 KB	Ok
22	Correct	8 ms	1484 KB	Ok
23	Correct	3 ms	1484 KB	Ok
24	Correct	2 ms	1484 KB	Ok
25	Correct	3 ms	1484 KB	Ok
26	Correct	2 ms	1484 KB	Ok
27	Correct	2 ms	1484 KB	Ok
28	Correct	2 ms	1484 KB	Ok
29	Correct	3 ms	1484 KB	Ok
30	Correct	2 ms	1484 KB	Ok
31	Correct	3 ms	1484 KB	Ok
32	Correct	2 ms	1484 KB	Ok
33	Correct	2 ms	1484 KB	Ok
34	Correct	5 ms	12744 KB	Ok
35	Correct	4 ms	12744 KB	Ok
36	Correct	4 ms	12744 KB	Ok
37	Correct	4 ms	12744 KB	Ok
38	Correct	3 ms	12744 KB	Ok
39	Correct	3 ms	12744 KB	Ok
40	Correct	3 ms	12744 KB	Ok
41	Correct	7 ms	12744 KB	Ok
42	Correct	6 ms	12744 KB	Ok
43	Correct	5 ms	12744 KB	Ok
44	Correct	7 ms	12744 KB	Ok
45	Correct	6 ms	12744 KB	Ok
46	Correct	7 ms	12744 KB	Ok
47	Correct	6 ms	12744 KB	Ok
48	Correct	6 ms	12744 KB	Ok
49	Correct	5 ms	12744 KB	Ok
50	Correct	6 ms	12744 KB	Ok
51	Correct	5 ms	12744 KB	Ok
52	Correct	7 ms	12744 KB	Ok
53	Correct	10 ms	12744 KB	Ok
54	Correct	59 ms	12744 KB	Ok
55	Correct	68 ms	12744 KB	Ok
56	Correct	67 ms	12744 KB	Ok
57	Correct	50 ms	12744 KB	Ok
58	Correct	71 ms	12744 KB	Ok
59	Correct	72 ms	12744 KB	Ok
60	Correct	59 ms	12744 KB	Ok
61	Correct	120 ms	12744 KB	Ok
62	Correct	118 ms	12744 KB	Ok
63	Correct	65 ms	12744 KB	Ok
64	Correct	70 ms	12744 KB	Ok
65	Correct	67 ms	12744 KB	Ok
66	Correct	62 ms	12744 KB	Ok
67	Correct	51 ms	12744 KB	Ok
68	Correct	75 ms	12744 KB	Ok
69	Correct	143 ms	12744 KB	Ok
70	Correct	133 ms	12744 KB	Ok
71	Correct	119 ms	12744 KB	Ok
72	Correct	157 ms	12744 KB	Ok
73	Correct	127 ms	12744 KB	Ok
74	Correct	120 ms	12744 KB	Ok
75	Correct	141 ms	12744 KB	Ok
76	Correct	151 ms	12744 KB	Ok
77	Correct	114 ms	12744 KB	Ok
78	Correct	143 ms	12744 KB	Ok
79	Correct	161 ms	12744 KB	Ok
80	Correct	127 ms	12744 KB	Ok
81	Correct	150 ms	12744 KB	Ok
82	Correct	129 ms	12744 KB	Ok
83	Correct	123 ms	12744 KB	Ok

Subtask #7
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Ok
2	Correct	2 ms	376 KB	Ok
3	Correct	2 ms	472 KB	Ok
4	Correct	3 ms	584 KB	Ok
5	Correct	2 ms	636 KB	Ok
6	Correct	2 ms	640 KB	Ok
7	Correct	2 ms	704 KB	Ok
8	Correct	2 ms	708 KB	Ok
9	Correct	2 ms	712 KB	Ok
10	Correct	3 ms	716 KB	Ok
11	Correct	3 ms	720 KB	Ok
12	Correct	2 ms	724 KB	Ok
13	Correct	3 ms	728 KB	Ok
14	Correct	3 ms	744 KB	Ok
15	Correct	3 ms	900 KB	Ok
16	Correct	2 ms	900 KB	Ok
17	Correct	2 ms	900 KB	Ok
18	Correct	4 ms	908 KB	Ok
19	Correct	10 ms	1316 KB	Ok
20	Correct	7 ms	1316 KB	Ok
21	Correct	12 ms	1484 KB	Ok
22	Correct	8 ms	1484 KB	Ok
23	Correct	3 ms	1484 KB	Ok
24	Correct	2 ms	1484 KB	Ok
25	Correct	3 ms	1484 KB	Ok
26	Correct	2 ms	1484 KB	Ok
27	Correct	2 ms	1484 KB	Ok
28	Correct	2 ms	1484 KB	Ok
29	Correct	3 ms	1484 KB	Ok
30	Correct	2 ms	1484 KB	Ok
31	Correct	3 ms	1484 KB	Ok
32	Correct	2 ms	1484 KB	Ok
33	Correct	2 ms	1484 KB	Ok
34	Correct	2 ms	1484 KB	Ok
35	Correct	2 ms	1484 KB	Ok
36	Correct	2 ms	1484 KB	Ok
37	Correct	2 ms	1484 KB	Ok
38	Correct	3 ms	1484 KB	Ok
39	Correct	78 ms	9896 KB	Ok
40	Correct	73 ms	9896 KB	Ok
41	Correct	137 ms	11564 KB	Ok
42	Correct	135 ms	11564 KB	Ok
43	Correct	69 ms	11564 KB	Ok
44	Correct	171 ms	12744 KB	Ok
45	Correct	5 ms	12744 KB	Ok
46	Correct	4 ms	12744 KB	Ok
47	Correct	4 ms	12744 KB	Ok
48	Correct	4 ms	12744 KB	Ok
49	Correct	3 ms	12744 KB	Ok
50	Correct	3 ms	12744 KB	Ok
51	Correct	3 ms	12744 KB	Ok
52	Correct	7 ms	12744 KB	Ok
53	Correct	6 ms	12744 KB	Ok
54	Correct	5 ms	12744 KB	Ok
55	Correct	7 ms	12744 KB	Ok
56	Correct	6 ms	12744 KB	Ok
57	Correct	7 ms	12744 KB	Ok
58	Correct	6 ms	12744 KB	Ok
59	Correct	6 ms	12744 KB	Ok
60	Correct	5 ms	12744 KB	Ok
61	Correct	6 ms	12744 KB	Ok
62	Correct	5 ms	12744 KB	Ok
63	Correct	7 ms	12744 KB	Ok
64	Correct	10 ms	12744 KB	Ok
65	Correct	59 ms	12744 KB	Ok
66	Correct	68 ms	12744 KB	Ok
67	Correct	67 ms	12744 KB	Ok
68	Correct	50 ms	12744 KB	Ok
69	Correct	71 ms	12744 KB	Ok
70	Correct	72 ms	12744 KB	Ok
71	Correct	59 ms	12744 KB	Ok
72	Correct	120 ms	12744 KB	Ok
73	Correct	118 ms	12744 KB	Ok
74	Correct	65 ms	12744 KB	Ok
75	Correct	70 ms	12744 KB	Ok
76	Correct	67 ms	12744 KB	Ok
77	Correct	62 ms	12744 KB	Ok
78	Correct	51 ms	12744 KB	Ok
79	Correct	75 ms	12744 KB	Ok
80	Correct	143 ms	12744 KB	Ok
81	Correct	133 ms	12744 KB	Ok
82	Correct	119 ms	12744 KB	Ok
83	Correct	157 ms	12744 KB	Ok
84	Correct	127 ms	12744 KB	Ok
85	Correct	120 ms	12744 KB	Ok
86	Correct	141 ms	12744 KB	Ok
87	Correct	151 ms	12744 KB	Ok
88	Correct	114 ms	12744 KB	Ok
89	Correct	143 ms	12744 KB	Ok
90	Correct	161 ms	12744 KB	Ok
91	Correct	127 ms	12744 KB	Ok
92	Correct	150 ms	12744 KB	Ok
93	Correct	129 ms	12744 KB	Ok
94	Correct	123 ms	12744 KB	Ok
95	Correct	145 ms	12744 KB	Ok
96	Correct	239 ms	12744 KB	Ok
97	Correct	213 ms	12744 KB	Ok
98	Correct	196 ms	12744 KB	Ok
99	Correct	259 ms	12744 KB	Ok
100	Correct	242 ms	12744 KB	Ok
101	Correct	255 ms	12744 KB	Ok
102	Correct	194 ms	12744 KB	Ok
103	Correct	262 ms	12744 KB	Ok
104	Correct	236 ms	12744 KB	Ok
105	Correct	276 ms	12744 KB	Ok
106	Correct	206 ms	12744 KB	Ok
107	Correct	236 ms	12744 KB	Ok
108	Correct	225 ms	12744 KB	Ok
109	Correct	325 ms	12744 KB	Ok
110	Correct	629 ms	41264 KB	Ok
111	Correct	599 ms	42184 KB	Ok
112	Correct	615 ms	42184 KB	Ok
113	Correct	652 ms	42184 KB	Ok
114	Correct	710 ms	42184 KB	Ok
115	Correct	541 ms	42184 KB	Ok
116	Correct	597 ms	42184 KB	Ok
117	Correct	587 ms	42184 KB	Ok
118	Correct	601 ms	42184 KB	Ok
119	Correct	579 ms	42184 KB	Ok
120	Correct	662 ms	42184 KB	Ok
121	Correct	535 ms	42184 KB	Ok
122	Correct	612 ms	42184 KB	Ok
123	Correct	592 ms	42184 KB	Ok
124	Correct	566 ms	42184 KB	Ok
125	Correct	382 ms	42184 KB	Ok

답안 #50910

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 9.0 / 9.0

Subtask #3 14.0 / 14.0

Subtask #4 15.0 / 15.0

Subtask #5 14.0 / 14.0

Subtask #6 18.0 / 18.0

Subtask #7 24.0 / 24.0

Subtask #1
6.0 / 6.0

Subtask #2
9.0 / 9.0

Subtask #3
14.0 / 14.0

Subtask #4
15.0 / 15.0

Subtask #5
14.0 / 14.0

Subtask #6
18.0 / 18.0

Subtask #7
24.0 / 24.0